《剑指offer》– 链表中倒数第k个节点、反转链表、合并两个排序的链表

一、链表中倒数时第k个节点：

1、题目：

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

2、解题思路：单链表具有单向移动的特性。

（1）第一种：先遍历链表，算出链表节点数count，第二次直接遍历到第count-k个节点。但是要注意，可能链表节点数count小于k，此时要返回NULL，所以要先判断这个条件。（这一种就不贴代码出来了）

（2）第二种：

可以用两个指针，一个指针遍历到第k个结点的时候，第二个指针再走到第一个节点，然后两个指针的距离始终保持k-1，这样，当第一个指针的next==NULL，也就是走到最后一个节点的时候，第二个指针对应的位置，就是倒数第k个结点。

这样的好处是能够节省一个循环，时间复杂度会相应降低。从Q(2N) 到Q(N)

注意，但是需要一个小循环让第一个指针先走到第k个指针。同时也存在结点总数小于k的问题，如果循环还没有进行到k次，而第一个指针的已经是NULL，即走到头了，那么，函数返回NULL。

3、代码实现：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

        if(head ==null || k<=0){
            return null;
        }
        ListNode last=head;
        
        //第一个指针先移动k-1个节点
        for(int i=0;i<k-1;i++){
            if(head.next!=null){
                head=head.next;
            }else{
                return null;
            }
        }
        //同时移动两个指针，当第一个指针指向null的时候，last就是所求的结点
        while(head.next!=null){
            head=head.next;
            last=last.next;
        }
        
        return last;
    }
}

二、反转链表：

参考博客：https://www.jianshu.com/p/e385d9c06672

1、题目：

输入一个链表，反转链表后，输出新链表的表头。

2、解题思路：

2-1：第一种：使用递归方式：

（1）解题思路：

假设链表为[1,2,3,4,5]先迭代到链表末尾5，然后从5开始依次反转整个链表。
如下图所示，先迭代待最后一位5，并且设置一个新的节点newList作为反转后链表的头结点，由于整个链表反转后的头就是最后一个数，所以newList存放的一直是反转后的头结点的地址，将head指向的地址赋值给head->next->next指针，并且一定要记得让head->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层head->next->next赋值的时候会覆盖后续的值。依次反转。。

（2）代码实现：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //递归方式
        if(head==null || head.next==null){
            return head;
        }
        ListNode newList=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        
        return newList;
    }
}

2-2第二种：使用迭代方式：

（1）解题思路：

先给定一个空的链表newList，然后判断传入的链表head是不是空链表或者链表元素只有一个，如果是，直接返回就可以。如果不是，则对链表进行迭代，然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp，就这样一直迭代完整个链表，返回newList就可以。如下图所示：

（2）代码实现：

 public ListNode ReverseList(ListNode head) {
        
        //非递归方式：
        ListNode newList=null;
        if(head==null || head.next==null){
            return head;
        }
        
        while(head!=null){
            ListNode temp=head.next;
            head.next=newList;
            newList=head;
            head=temp;
        }
        return newList;
    }

三、合并两个排序的链表：

参考博客：https://blog.csdn.net/qq_23217629/article/details/51730312

1、题目：

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

2、解题思路：

比较两个链表的第一个节点，取出最小值的节点，接着再按照相同的方式重复比较剩余链表的节点。

3、代码实现：

public class Solution {
    public ListNode Merge1(ListNode list1, ListNode list2) {
            //递归版本
			ListNode head;
			if (list1 == null) {
				return list2;
			}
			if (list2 == null) {
				return list1;
			}
			if (list1.val < list2.val) {
				head = list1;
				head.next = Merge(list1.next, list2);
			} else {
				head = list2;
				head.next = Merge(list1, list2.next);
			}
			return head;
		}

    public ListNode Merge(ListNode list1,ListNode list2) {
		//非递归版本：
		ListNode head = new ListNode(-1);//头节点，用来存储合并的链表
		head.next = null;
		ListNode root = head;//root暂存我新建的头节点，合并之后返回root.next，就是题目给的头节点
		
		while(list1!=null && list2!=null){
			if(list1.val <=list2.val){
				head.next=list1;
				head = list1;
				list1 = list1.next;
			}else{
				head.next=list2;
				head=list2;
				list2=list2.next;
			}
		}
		
		//把未结束的链表连接到合并后的链表尾部
		if(list1 !=null){
			head.next=list1;
		}
		if(list2 !=null){
			head.next=list2;
		}
		
		return root.next;
    }
}