代码随想录训练营Day4| 两两交换链表中的节点、删除链表的倒数第N个结点、链表相交、环形链表II

两两交换链表中的节点

文章：代码随想录 (programmercarl.com)

题目：24. 两两交换链表中的节点

视频：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili（尊嘟讲的很好，可以去看看！）

奇数节点：最后会多出来一个节点，但是因为没有多出来的节点可以和其交换，所以我们不交换最后一个节点

偶数节点：两两交换即可

【思路】

• 虚拟头结点

  我们当前操作的指针，一定要指向我们要反转的两个节点的前一个节点

  cur 指向2，然后2指向1，1再指向3，拉直链表之后，即完成了节点12的交换

• 遍历的终止条件一定要清楚！

• 进行两两交换的逻辑一定要清楚

• Java实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        //虚拟头结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode cur = dummyNode;
        while(cur.next != null && cur.next.next!= null){
            ListNode temp = cur.next; //1
            ListNode temp1 = cur.next.next.next; // 3

            cur.next = cur.next.next;//cur -> 2
            cur.next.next = temp;  // 2 -> 1
            temp.next = temp1;//1 -> 3
            cur = cur.next.next; //cur -> 3  这里写的时候出现错误，写多了一个next，还是对指针不够熟悉
        }
        return dummyNode.next;
    }
}

• Go实现

func swapPairs(head *ListNode) *ListNode {
    dummyNode := &ListNode{0,head}
    cur := dummyNode
    for cur.Next != nil && cur.Next.Next != nil{
        temp := cur.Next
        temp1:= cur.Next.Next.Next

        cur.Next = cur.Next.Next
        cur.Next.Next = temp
        temp.Next = temp1
        cur = cur.Next.Next//这里还是写错了，cur最后是移动到被修改的第二个指针1 处！
    }
    return dummyNode.Next

}

---

删除链表的倒数第N个结点

文章：6. 删除链表的倒数第N个节点

题目：19. 删除链表的倒数第 N 个结点

【思路】

本题是我自己想出来的办法（一年前有写过该题），大概思路为使用快慢指针，先将fast指针提前先走N步，随后fast和slow指针一起遍历，直到fast指针的next为空（即fast指针已经指向链表的末尾），这时prev指针指向的正好是需要删除的倒数第N-1个结点处。我们只需要修改第N-1个结点的next指针即可完成对倒数第N个结点的删除。

• Java实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode cur = dummyNode;
        ListNode prev = dummyNode;//修改为指向dummyNode

        //这个方法的问题在于无法通过[1]这个测试用例
        //经修改，快慢指针的情况下，最好让两个指针在一开始就初始化相同起点，后面会更加好操作不会混乱
        for(int i = 0 ;i < n;i++){ // <n !!
            cur = cur.next;
        }
        while( cur.next!= null){
            cur = cur.next;
            prev = prev.next;
        }
        prev.next = prev.next.next;
        return dummyNode.next;

    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyNode := &ListNode{}
    dummyNode.Next = head
    fast := dummyNode
    slow := dummyNode

    for i:= 0 ;i < n;i++{
        fast = fast.Next
    }
    for fast.Next != nil{
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return dummyNode.Next//漏了.Next指针，搞得一直多一个0出来、、、
}

---

链表相交

文章：7. 链表相交

题目：面试题 02.07. 链表相交

• Java实现

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode dummyNodeA = headA;
        ListNode dummyNodeB = headB;

        while(dummyNodeA != null){
            lenA++;
            dummyNodeA = dummyNodeA.next;
        }
        while(dummyNodeB !=null){
            lenB++;
            dummyNodeB = dummyNodeB.next;
        }
        dummyNodeA = headA;
        dummyNodeB = headB;
        /*if(lenA > lenB){
            for(int i = 0 ; i < lenA-lenB;i++){
                dummyNodeA = dummyNodeA.next;
            }
        }
        else if(lenB > lenA){
            for(int i =0 ;i < lenB - lenA;i++){
                dummyNodeB = dummyNodeB.next;
            }
        }*/
        //如果B链表比A链表长，交换AB链表
        if(lenB > lenA){
            //交换长度
            int temlem = lenA;
            lenA = lenB;
            lenB = temlem;
            //交换链表：直接交换头指针就好噜，是链表的方便之处！
            ListNode temNode = dummyNodeA;
            dummyNodeA = dummyNodeB;
            dummyNodeB = temNode;
        }
        //到此，我们已经成功的将A链表设置为最长的链表，然后我们需要将A链表与B链表进行对齐操作
        int gap = lenA - lenB;
        while(gap -- > 0){
            dummyNodeA = dummyNodeA.next;
        }
        //这里已经默认了A链表为最长的链表，但是我前面并没有将A链表置为最长&&并且存在超过相交值的可能性！
        while(dummyNodeA != null){//不需要.next，找到当前指针就够了
            if(dummyNodeA == dummyNodeB){ //是指针地址相同，不是指针的值相同
                return dummyNodeA;
            }
            dummyNodeA = dummyNodeA.next;
            dummyNodeB = dummyNodeB.next;
        }
        return null;
    }
}

• Go实现

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA ,lenB := 0 , 0 
    dummyA , dummyB := headA,headB
    for dummyA!= nil{
        lenA+=1
        dummyA = dummyA.Next
    }
    for dummyB != nil{
        lenB+=1
        dummyB = dummyB.Next
    }
    dummyA ,dummyB = headA,headB
    if lenA < lenB{
        lenA,lenB = lenB,lenA
        dummyA,dummyB = dummyB,dummyA
    }
    gap := lenA-lenB
    for gap >0 {
        dummyA = dummyA.Next
        gap--
    }
    for dummyA != nil {
        if dummyA == dummyB{
            return dummyA
        }
        dummyA = dummyA.Next
        dummyB = dummyB.Next
    }
    return nil
}

---

环形数组II

• 判断链表是否有环
• 找到环的入口

【思路】

• 快慢指针，如果链表有环，快慢指针会相遇
• Java实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next !=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                ListNode index1 = fast;
                ListNode index2 = head;
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

• Go实现

func detectCycle(head *ListNode) *ListNode {
    fast,slow := head,head
    for fast != nil && fast.Next != nil{
        fast = fast.Next.Next
        slow = slow.Next
        if(fast == slow){
            index1 , index2 := fast,head
            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil
}

---

【算法总结】

• 两两交换链表中的节点采用虚拟头结点的方式来两两交换节点，交换完后虚拟节点直接去第三个节点；需要注意循环的终止条件！
• 删除链表的倒数第N个节点采用快慢指针的方式进行节点删除，通过保持快指针和慢指针之间的距离来对倒数第N个节点进行操作；需要注意快慢指针最好是同一个起点，这样比较方便判断！同时需要注意循环的终止条件！
• 链表相交采用判断链表长度、交换链表头结点、将两链表的长度对齐的方法进行是否相交的判断；需要注意是判断指针是否相同，而不是判断指针的值是否相同
• 环形数组II采用快慢指针的方式来判断链表是否有环、寻找环的入口在哪；需要注意循环的终止条件，（易错点）很容易循环到null值！；不得不说卡尔劳斯的推导真的很精彩，感谢！

需要强调的一点：需要注意指针next属性的使用，很容易跳过头出现nullORnil的情形。