每日一题之《剑指offer》14,15,16题

第十四题：链表中倒数第k 个节点

难易度：⭐

题目描述：
现有节点类：

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

    ListNode(int val) {
        this.val = val;
    }
}

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

一般的思路是：从头节点开始遍历链表，记录链表的长度 n ，然后再次从头开始遍历，遍历到第n-k+1个节点处，返回即可，不过要注意的是需要判断几种case:如果链表为空时直接返回空即可，如果k > 链表的长度 n 或者 k <= 0 时，返回空,代码如下：

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode cur = head;
        int listLen = 0;
        while(cur != null){
            cur = cur.next;
            listLen++;
        }
        if(k > listLen){
            return null;
        }
        for(int i = 1;i <= listLen - k;i++){
            head = head.next;
        }
        return head;
    }
}

这样做，很显然是可以的，但是能不能仅仅遍历一次链表就可以得到链表中倒数第k个节点呢？
思路：
准备一个指针 behind，等到cur指针遍历到链表的正数第k个位置时，behind 指针再从0位置出发，等到cur指针走完，behind会正好停在整个链表的倒数第k个位置。需要注意的是，我们也要判断各种case,如果k 的值要比 整个链表的长度还大，如何处理，这些细节是本题的关键。
代码如下：

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k <= 0){
            return null;
        }
        ListNode cur = head;
        ListNode behind = head;
        for(int i = 0;i < k;i++){
            if(cur != null){
                cur = cur.next;
            }else{
                return null;
            }
        }
        while(cur != null){
            cur = cur.next;
            behind = behind.next;
        }
        return behind;
    }
}

第十五题：反转链表

难易度：⭐

题目描述：
给定链表的节点类
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
输入一个链表，反转链表后，输出新链表的表头。

本题是最简单的链表类问题了，应该熟练到可以白板coding秒写的程度，此处也就不再画图演示这个过程了，通过代码也可以知道整个过程是怎么发生的。其他的方法肯定没有经典代码优秀，不建议使用，还是老老实实遵循这种经典教科书的写法。

代码如下：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

第十六题：合并两个排序的链表

难易度：⭐⭐

题目描述
有链表的节点类
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
输入两个单调递增的链表，输出两个链表合成后的链表;
当然我们需要合成后的链表满足单调不减规则。

本题是链表的归并排序，我们都熟知数组的排序。链表同数组是一样的，都是线性数据结构，数组可以的排序，在链表上自然也行得通。如果不熟悉归并排序的朋友，可以参考下我的文章，理解下归并排序
时间复杂度的认识,递归,归并排序
归并排序非常重要，如果你知道数组怎么样排序，链表其实也是一样的，此处就不解释说明merge的过程了
代码如下：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null){
            return null;
        }
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }else{
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        if(list1 != null){
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2;
        }
        return dummyHead.next;
    }    
}

本题中，我使用了dummyHead,作为新的链表头结点的头结点，这样做的原因是可以在merge的过程中，更简便地使用引用的指向，如果不使用dummyHead，那么一定程度上，你的代码会稍稍复杂那么一点点。使用了dummyHead后，最后结果返回dummyHead.next即可。除了归并写法，本题还可以使用经典的递归写法：
代码如下：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null){
            return null;
        }
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val < list2.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }else{
            list2.next = Merge(list2.next,list1);
            return list2;
        }
    }    
}

递归的解决方法，更是简单明了。