《剑指offer》– 两个链表的第一个公共结点、链表中环的入口结点、删除链表中的重复结点

一、两个链表的第一个公共结点：

1、题目：

输入两个链表，找出它们的第一个公共结点。

2、解题思路：

（1）第一种：找出两个链表的长度，然后让长的链表先走两个链表的长度差，接着两个链表一起走。

（2）第二种：用两个指针扫描”两个链表”，最终两个指针到达 null 或者到达公共结点。接着，把链表1的尾连到链表2的头，把链表2的尾连到链表1的头，同时遍历，最终会在公共结点相遇；

3、代码实现：

public class Test9 {
	
	//解题方法二：找出两个链表的长度，然后让长的先走两个链表的长度差，然后一起走
	public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		int length1 = listLength(pHead1);
		int length2 = listLength(pHead2);
		
		if(length1>length2){
			pHead1= walkStep(pHead1,length1-length2);
		}else{
			pHead2 = walkStep(pHead2,length2-length1);
		}
		while(pHead1 != null){
			if(pHead1 == pHead2) return pHead1;
			pHead1 = pHead1.next;
			pHead2 = pHead2.next;
		}
		return null;
	}
	//判断两个链表的的长度
	public int listLength(ListNode listNode){
		if(listNode == null) return 0;
		int length=0;
		while(listNode != null){
			listNode = listNode.next;
			length++;
		}
		return length;
	}
	//长度较长的链表先移动长度差
	public ListNode walkStep(ListNode listNode,int step){
		while(step>0){
			listNode = listNode.next;
			step--;
		}
		return listNode;
	}
	
	
	//解题思路一：用两个指针扫描"两个链表"，最终两个指针到达 null 或者到达公共结点。
	//把链表1的尾连到链表2的头，把链表2的尾连到链表1的头，同时遍历，最终会在公共结点相遇；
	public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
		 ListNode p1=pHead1;
		 ListNode p2=pHead2;
		 while(p1 != p2){
			 p1=(p1==null ? pHead2 : p1.next);
			 p2=(p2==null ? pHead1 : p2.next);
		 }
		return p1;
    }
}


class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

二、链表中环的入口结点：

1、题目：

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

2、解题思路：

参考牛客网的“求一个大大的offer”：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程）

当快慢指针相遇的时候：

此时慢指针走的路程为Sslow = x + m * c + a
快指针走的路程为Sfast = x + n * c + a
2 Sslow = Sfast
2 * ( x + m*c + a ) = (x + n *c + a)
从而可以推导出：
x = (n – 2 * m )*c – a
= (n – 2 *m -1 )*c + c – a
即环前面的路程 = 数个环的长度（为可能为0） + c – a
什么是c – a？这是相遇点后，环后面部分的路程。（橙色路程）
所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，
2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x）
从相遇点开始走的那个指针也一定刚好到达环入口点。
所以2者会相遇，且恰好相遇在环的入口点。

最后，判断是否有环，且找环的算法复杂度为：

时间复杂度：O(n)  ， 空间复杂度：O(1)

3、代码实现：

public class Test13 {
	 public ListNode EntryNodeOfLoop(ListNode pHead){
		 	
		 if(pHead == null  || pHead.next == null || pHead.next.next == null) return null;
		 ListNode fast=pHead.next.next;
		 ListNode slow=pHead.next;
		 
		 //先判断有没有环
		 while(fast!=slow){
			 if(fast.next !=null && fast.next.next !=null){
				 fast=fast.next.next;
				 slow=slow.next;
			 }else{
				 //没有环，则返回
				 return null;
			 }
		 }
		 
		 //循环出来就是有环，且此时fast==slow
		 fast=pHead;
		 while(fast != slow){
			 fast = fast.next;
			 slow = slow.next;
		 }
		 
		 return slow;
    }
}


class ListNode {
    int val;
    ListNode next = null;

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

三、删除链表中的重复结点：

1、题目：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

2、解决思路：

使用递归的方式：

3、代码实现：

public class Test14 {

	public ListNode deleteDuplication(ListNode pHead){
		if(pHead == null ){
			return null;
		}
		if(pHead !=null && pHead.next==null){
			return pHead;
		}
		
		ListNode current;
		if(pHead.next.val == pHead.val){
			current = pHead.next.next;
			while(current!=null &&current.val == pHead.val){
				current = current.next;
			}
			return deleteDuplication(current);
		}
		else{
			current = pHead.next;
			pHead.next=deleteDuplication(current);
			return pHead;
		}
    }
}


class ListNode {
    int val;
    ListNode next = null;

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