查找两个相交链表的第一个相交节点

题目：输入两个链表，找出它们的第一个公共节点。
示例：① listA = {4,1,8,4,5}
istB = {5,0,1,8,4,5}
结果返回 1 。

② listA = {}
listB = {1,2,3}
返回 null。

思路： ① 判断两个链表是否为空，如果有一个为空，直接返回null。
② 计算两个列表的长度，算出长度差，记作 dist。
③ 声明两个快慢引用 slow和fast，让快引用fast指向长链表。
④ 让快引用fast，先往前走dist的距离。
⑤ fast、slow同时向前走，边走边判断两个引用是否指向同一个位置。
要注意：while循环里的条件判断。

代码实现：

public class Solution {
       public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
  // 声明两个快慢指针。
        ListNode fast = null;
        ListNode slow = null;
        if(pHead1==null || pHead2==null){
            return null;
        }
//         // 先计算A链表和B链表的长度。
        int listA_length = getLength(pHead1);
        int listB_length = getLength(pHead2);
        // 计算长度差
        int dist = Math.abs(listA_length-listB_length);
        if(listA_length > listB_length){
            fast = pHead1;
            slow = pHead2;
        }else{
            fast = pHead1;
            slow = pHead2;
        }
        //让快指针 先走 dist
        for(int i = 0;i<dist;i++){
            fast = fast.next;
        }
        // 快慢引用同时向前走，如果两个引用指向的地址值相同，则说明当前节点是我们的相交节点。
        while(slow!=null && fast!=null ){
            if(fast==slow){
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
}
    public int getLength(ListNode a){
        ListNode ptr = a;
        int length = 0;
        if(ptr==null) return 0;
        while(ptr!=null){
            ptr = ptr.next;
            length++;
        }
        return length;
    }
}

反转链表

题目： 输入一个链表，将其反转，并返回头结点。
示例： 输入：{1,2,3}
输出：{3,2,1}
思路：
① 判断链表是否为空，若为空，返回null。
② 定义三个引用，分别记为 prev、cur、next。表示前驱、当前、后继
③ 让cur指向原链表第一个节点。prev置为空，next置为空。
④ 在不断的遍历链表时，通过这三个引用，改变链表结构。
⑤ 即就是 用next保存当前链表的下一个节点，以便下次循环找到位置。将cur的next指向prev，然后移动prev至cur位置，cur又移动到next的位置。从而达到反转链表的目的。

在不断的遍历中，通过改变cur与prev之间的关系，从而进行反转链表的操作。

next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
具体代码：

    public ListNode ReverseList(ListNode head) {
        ListNode cur = head;
        if(cur==null){
            return null;
        }
        ListNode prev = null;
        ListNode next  = null;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

合并两个有序链表

题目：将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。

思路： ① 首先需要判断，给定的两个链表A、B是否为空。如果都为空，返回null。如果A为空，则返回B，如果B为空，则返回A。
② 比较两个A、B链表的第一个节点，若A链表的第一个节点小，则把A链表中第一个节点置为新链表的第一个节点。反之，将B链表中的第一个节点置为新链表的第一个节点。此时需要一个变量，指向新链表的第一个节点 记作：newHead。
③ 通过遍历比较两个链表中的节点值，哪个小，就把哪个移动到新链表中。

④ 给定一个临时指针指向新链表的第一个节点，记作 tmp。这个临时指针用于遍历新链表，并向新链表中插入值。

比较l1和l2的第一个节点，l1的小，此时l1向后走，newHead指向2。

接着 遍历l1和l2，哪个小，就插入到新链表中。

代码实现：

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
       ListNode newHead = null; // 新链表的第一个节点
        // 先判断两链表是否为空
        if(l1 == null && l2 == null){
            return null;
        }
        //若l1为空，则直接返回l2
        if(l1 == null){
            return l2;
        }
        //若l2为空，则直接返回l1
        if(l2 == null){
            return l1;
        }        
        // 比较两个链表第一个节点的大小，较小的做为新链表的第一个节点
        if(l1.val <=l2.val){
            newHead = l1;
            l1 = l1.next;
        }else{
            newHead = l2;
            l2 = l2.next;
        }
        ListNode tmp = newHead; // 用于遍历新链表
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
            }else{
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        // 跳出while循环无非就是两种情况
        // 要么l1为空，说明已经把l1遍历完了，则把l2剩下的插入
        if(l1==null){
            tmp.next = l2;
        }
        if(l2==null){
            tmp.next = l1;
        }
        return newHead;
    }

判断链表中是否有环

题目： 判断一个链表中是否有环。
示例：
该链表的环是由： 4 5 6 7 8组成的。

思路：
① 判断是否有环问题。我们可以把它看成类似于你追我跑的问题。
② 我们可以定义两个快慢引用，分别记作 slow、fast
③ 我们让快引用fast每次向前走两个，慢引用slow每次向前走一个。
④ 当slow==fast时，就说明，链表中有环。
⑤ 注意特殊情况： 当链表为空，或者链表中只有一个节点时，不构成环。
注意while循环里的条件判断

代码实现：

public boolean hasCycle(ListNode head) {
        if(head==null || head.next == null){
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null && slow!=null && fast!=slow){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast==slow){
            return true;
        }
        return false;
    }

删除链表中重复的元素

题目：
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

示例：给出的链表为1->1->2 返回 1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

思路：
① 先判断链表是否为空，若为空，直接返回null。
② 如果链表不为空，我们给定一个引用，记作tmp。目的是遍历链表
③ 通过遍历，判断前一个节点和下一个节点是否相等。即 tmp.val == tmp.next.val
④ 如果相等，则让tmp所指的节点的next域 指向这个节点的下一个的下一个，即tmp.next.next
⑤ 因为链表是有序的，如果不相等，则让tmp指向tmp的下一个节点，然后继续判断。
注意 while循环里的判断条件

比如： 1 -> 1 -> 1 -> 2
① ② ③ ④
节点① 和节点②相同，则让节点① 指向节点③，这个时候还不能让tmp进行tmp = tmp.next操作。
因为防止后面还有相同的元素，所以，这里我们继续比较。 此时tmp指向①。tmp的next指向③
再比较tmp.val == tmp.next.val？ 如果相同，则继续删除，此时 节点①指向节点④ 然后在比较，①和④的值不相同，此时再让tmp = tmp.next；

代码实现：

 public ListNode deleteDuplicates (ListNode head) {
        if(head == null){return null;}
        ListNode tmp = head;
        while(tmp.next!=null){
            if(tmp.val == tmp.next.val){
                tmp.next = tmp.next.next;
            }else{
                tmp = tmp.next;
            }
        }
        return head;
    }

链表中环的入口节点

题目：
给出一个链表，找出该链表中环的入口节点。
示例：
该链表的环的入口节点为 2 。

思路：
① 链表是否为空，若空，返回null。
② 若不空，判断是否存在环，若不存在环 返回null
定义两个指针slow,fast。让slow和fast都指向链表的头部，让fast每次往前走两步，slow每次往前走一步。如果fast和slow相遇了，则说明存在环。
③ 定义一个指针，用于标记slow和fast相遇的节点，记作meetNode。
④ 此时新定义一个新指针，指向链表的头部。记作 tmp。同时让tmp和meetNode以相同的步长往前走
⑤ 若tmp 与 meetNode 相等，则说明，tmp和meetNode共同指向的位置 就是环的入口节点。

证明
X,Y,Z分别为链表起始位置，环开始位置和两指针相遇位置。慢指针的速度设为 x，则快指针的速度为2x。
快慢指针均从X出发，在Z相遇。此时，慢指针走的距离为：(a+b)，快指针走的距离为: a+b+n(b+c)。
所以， (a+b)/x = a+b+n(b+c)/2x，化简得：2(a+b) = a+b+n(b+c)
推出：
a = (n-1)b+nc = (n-1)(b+c)+c
即将此两指针分别放在起始位置和相遇位置，并以相同速度前进，当一个指针走完距离a时，另一个指针恰好走出 n-1圈加c的距离。
代码实现：

public class Solution {
    public ListNode isCycle(ListNode head){
        if(head==null || head.next==null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(slow!=null && fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return slow;
            }
        }
        return null;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode meetNode = isCycle(head);
        ListNode tmp = head;
        if(meetNode != null){
            while(tmp!=meetNode){
                tmp = tmp.next;
                meetNode = meetNode.next;
            }
            return meetNode;
        }
        return null;
    }
}

链表中倒数第k个节点

题目：
输入一个链表，输出该链表中倒数第k个结点。
如果该链表长度小于k，请返回空。
示例：
1->2->3->4->5->6，输出倒数第3个结点，输出结果为：4。

思路一：使用双指针
倒数第k个节点，就是正数第n-k+1个节点，我们可以定义两个指针分别记为：slow，fast。让fast先走k-1步。然后快慢指针一起向前走，当快指针走到最后一个节点时，慢指针所指的就是我们所要查找的节点。

代码实现：

    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode tmp = pHead;
        int num = 0;
        while(tmp!=null){
            num++;
            tmp = tmp.next;
        }
        if(k>num||k<=0){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i = 0; i<k-1;i++){
            fast = fast.next;
        }
        while(fast.next!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

思路二：使用栈
我们可以让链表中的节点全部入栈，倒数第k个节点，就是栈中第k个节点。
代码实现：

    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(k<=0){
            return null;
        }
        int tag = 0;
        int num = 0;
        Stack<ListNode> stack = new Stack<>();
        ListNode tmp = pHead;
        ListNode ptr = null;
        while(tmp!=null){
            num++;
            stack.push(tmp);
            tmp = tmp.next;
        }
        if(k>num){
            return null;
        }
        while(tag!=k && !stack.empty()){
            tag++;
            ptr = stack.pop();
        }
        return ptr;
    }

链表中的节点每k个一组进行翻转

题目：
将给出的链表中的节点每k个一组翻转，返回翻转后的链表如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样你不能更改节点中的值，只能更改节点本身。要求空间复杂度O(1)

示例：
给定的链表是1→2→3→4→5
对于 k=2, 你应该返回2→1→4→3→5
对于 k=3, 你应该返回3→2→1→4→5

思路：
① 确定每次要翻转节点的个数，假设k=2，则说明，每回要翻转节点的个数为2个。这里需要一个变量，用于记作要翻转链表的范围，记作end。
② 我们可以给定一个假节点，它相当于整个链表的头节点。
③ 我们确定end的时候，需要进行for循环，例：对于链表 1->2 -> 3 -> 4 -> 5来说，如果k=2，则我们每两个节点进行翻转。而end的作用就是找到每组链表的尾节点。
④ 当我们翻转链表时，可以给定一个指针：start，记录这一组链表的第一个节点，于是，这一组链表现在有了start，end两个指针。然后我们执行reverse()函数，翻转该组链表，当翻转完成后，我们需要拼接后面的链表。
然后再次让end找到下一组链表的尾结点。

图示：蓝色表示要翻转的链表，红色表示待翻转的链表，黄色表示已翻转的链表

我们指定k=2。

代码实现：

public ListNode reverseKGroup (ListNode head, int k) {
        if(head == null || head.next==null){
            return head;
        }
        // 定义一个假的节点
        ListNode dummy = new ListNode(0);
        // 假节点指向head
        dummy.next = head;
        // 初始化 pre和end指向dummy，pre指每次要翻转链表的第一个节点的上一个节点
        // end指每次要反转的链表的尾结点
        ListNode pre = dummy;
        ListNode end = dummy;
        while(end.next!=null){
            for(int i = 0; i<k && end!=null; i++){//这里的条件end!=null是为了防止还没有遍历k次，end
                                                //就为null，说明，剩下大的这组链表的个数小于k。
                end = end.next;
            }
            // 如果end为空，即需要反转的链表个数小于k，不反转
            if(end==null){
                break;
            }
            //先记录下end,next，方便后面连接链表
            ListNode next = end.next;
            // 与后面的链表断开连接。
            end.next = null;
            ListNode start = pre.next; //记录要进行反转的链表的头节点
            pre.next = reverse(start); //翻转链表，pre.next指向翻转后的链表。
            // 翻转下一组链表。
            start.next = next;
            pre = start;
            end = start;
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head){
        ListNode cur = head;
        ListNode behind = null;
        ListNode front = null;
        while(cur!=null){
            front = cur.next;
            cur.next = behind;
            behind =  cur;
            cur = front;
        }
        return behind;
    }

删除链表中的重复元素(重复的元素全删完)

题目：
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

示例： 给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

思路：
双指针法。
定义一个假节点,demmy,类似于头结点的作用。
demmy.next = head;
① 定义一个cur用于记录当前节点
② 定义一个prev，用于记录cur的前一个节点。

③ 遍历链表，当cur.val != cur.next.val 时，cur和prev同时向前。
④ 当cur.next == cur.next.val时，定义一个指针temp。
该指针的作用是，向后遍历，直到找到一个节点的值不等于cur的值为止。
然后将prev.next 指向 temp。cur指向temp。

代码实现：

 public ListNode deleteDuplicates (ListNode head) {
        ListNode demmy = new ListNode(-1);
        demmy.next = head;
        ListNode cur = head;
        ListNode prev = demmy;
        while(cur!=null && cur.next!=null){
            if(cur.val == cur.next.val){
                ListNode temp = cur.next;
                while(temp!=null&&temp.val==cur.val){
                    temp = temp.next;
                }
                prev.next = temp;
                cur = temp;
            }else{
                cur = cur.next;
                prev = prev.next;
            }
        }
        return demmy.next;
    }