Ciel's blog

面试题15-链表中倒数第k个结点

Posted on 2020-03-16 Edited on 2025-04-13 In 数据结构与算法

题目

输入一个链表，输出该链表中倒数第k个结点。

解题

本题可以先遍历链表计数节点个数n，然后让指针从头开始移动n-(k-1)个结点则找到了倒数第k个结点。但是更漂亮的办法是用两个指针，只遍历链表一次：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        // for robustness
        if (head == null || k == 0){
            return null;
        }
        ListNode node = head;
        int counter = 0;
        while (head != null){
            // for robustness
            if (head.next == null && counter<k-1){
                return null;
            }
            head = head.next;
            if (counter>k-1){
                node = node.next;
            }
            counter++;
        }
        return node;
    }
}

本题特别要注意的是代码的鲁棒性。可能的坑有三个：

输入head为空；
k大于链表结点总数；
k =0。

总结

注意找第k个结点，循环k-1次！对于这种边界条件不清楚的时候可以举简单的列子帮助自己清晰思路。
灵活运用双指针。类似的题目还有：
- 求链表的中间结点；
- 判断一个单项链表是否形成了环形结构。

references

《剑指offer》

面试题17-合并两个排序的链表

Posted on 2020-03-14 Edited on 2025-04-13 In 数据结构与算法

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题

合并过程（《剑指offer》）

非递归

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 注意这里不能传入null，也不能=null
        ListNode cur = new ListNode(0);
        // dummy head
        ListNode dummy = cur;
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        while (list1 != null && list2 != null){
            if (list1.val <= list2.val){
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1 != null) {
            cur.next = list1;
        } else if (list2 != null){
            cur.next = list2;
        }
        return dummy.next;
    }
}

递归法

每一个步骤都是相同的操作，所以是典型的递归过程，可以通过定义递归函数完成合并过程。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // 新建了一个list
        ListNode mergedList = null;
        // for robustness
        if (list1 == null){
            return list2;
        }
        if (list2 == null){
            return list1;
        }
        
        if (list1.val <= list2.val){
            mergedList = list1;
            mergedList.next = Merge(list1.next, list2);
        } else {
            mergedList = list2;
            mergedList.next = Merge(list1, list2.next);
        }
        return mergedList;
    }
}

其他

插入

自己最开始的思路是，从list2中一个一个取结点插入到list1中。下一次的插入可以只从上一次插入结点遍历到list1的尾结点。但是搅了半天还是没有写出正确的代码。看到牛客网上有人给出的类似解答如下：

把list2往list1的中插。

比较list2与list1的值：
当list2值小等于list1值时往list1的前面插，并让list2指向下一个元素
否则不进行插入，list1指向下一个结点。

重复上述操作，直到有一个链表为空

判断是哪个链表空了，如果是list2则说明list2已全部插入直接返回头结点即可。如果是list1，则将剩下的list2结点直接连到list1尾部，返回头结点即可。

链接：https://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337?answerType=1&f=discussion
来源：牛客网

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null ){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1 == null && list2 == null){
            return null;
        }
        //传入任意值初始化pre1，避免空指针异常。用于记录list1的前一个结点地址
        ListNode pre1 = new ListNode(-1);
        //用于记录list2的下一个结点地址
        ListNode p2 = null;
        //用于记录合并后链表的头结点。
        ListNode head = null;
        //如果list1的第一个结点值比list2第一个结点值小则用list1做表头
        if(list1.val < list2.val){
            head = list1;
        }else{
            //否则用list2做表头
            head = list2;
        }
        //当链表1和链表2都不为空时
        while(list1 != null && list2 != null){
            //如果list2的值小于等于list1则往list1前面插
            if(list2.val <= list1.val){
                p2 = list2.next;        //用p2保存list2的下一个结点
                list2.next = list1;     //把list2与list1相连
                pre1.next = list2;      //让list1的前一个结点指向list2
                pre1 = list2;           //此时list1的前一个结点变成list，更新pre1
                list2 = p2;             //list2指向下一个结点
            }else {                     //否则list1指向下一个结点
                pre1 = list1;          
                list1 = list1.next;
            }
        }
        if(list2 != null){              //插完需要判断list2是否还有值，将list2剩余值插入
            pre1.next = list2;
        }
        return head;
    }
}

递归优化

另外看到一个很优美的python题解：

def Merge(self, pHead1, pHead2):
    # write code here
    if pHead1 and pHead2:
        if pHead1.val > pHead2.val:
            pHead1, pHead2 = pHead2, pHead1
        pHead1.next = self.Merge(pHead1.next, pHead2)
    return pHead1 or pHead2

总结

类似于并归排序。
null只能赋值给引用类型的对象，不能赋值给基本的数据类型，如int。

References

牛客网讨论与题解

《剑指offer》

浅谈Java中的对象和引用

Java 基础篇 - 类与对象（对于引用类型和基本类型的参数传递讲得很清晰）