Day4代码随想录2* | 两两交换链表中的节点&&删除链表的倒数第N个节点&&链表相交&&环形链表II&&总结

24.两两交换链表中的节点

文章：5. 两两交换链表中的节点

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

【思路】

虚拟头结点

• Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //虚拟头结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode cur = dummyNode;
        while(head != null && head.next != null){
            cur.next = head.next;//2
            ListNode temp = head.next.next;//3
            head.next.next = head;
            head.next = temp;
            //更新
            cur = head;//负责殿后
            head = temp;

        }
        return dummyNode.next;
    }
}

• Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil{
        return head
    }
    dummy := &ListNode{-1,head}
    pre := dummy

    for  head!= nil && head.Next!= nil  {
       pre.Next = head.Next
       temp := head.Next.Next
       head.Next.Next = head
       head.Next = temp
       pre = head
       head = temp
       

    }
    return dummy.Next    
}

递归

暂时还没看懂

• Java

• Go

---

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

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

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

【思路】

虚拟头结点。让head指针先跑N个领先位置，然后cur指针（记录被删除节点的next）和pre指针（记录被删除节点的前一个指针）一起跑。当head == nil时说明cur指针已经指向倒数第n个节点、pre指针指向第n-1个节点，改一改就ok了。

• 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;

    }
}

• Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{-1,head}
    for head!=nil&&n > 0{
        head = head.Next
        n--
    }
    pre:=dummy
    cur := dummy.Next
    for head!= nil{
        head = head.Next
        pre = pre.Next
        cur = cur.Next
    }
    pre.Next = cur.Next

    return dummy.Next
    

}

---

链表相交

文章：7. 链表相交

题目：

【思路】

​ //同起点，然后一起比较val是否相同，相同就返回

• Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //同起点，然后一起比较val是否相同，相同就返回，
        int lenA = 0;
        int lenB = 0;
        ListNode dummyA = headA;
        ListNode dummyB = headB;
        while(dummyA != null){
            dummyA = dummyA.next;
            lenA++;
        }
        while(dummyB != null){
            dummyB = dummyB.next;
            lenB++;
        }
        if(lenA > lenB){
            int len = lenA - lenB;
            while(len>0){
                headA = headA.next;
                len--;
            }
        }else{
            int len = lenB-lenA;
            while(len>0){
                headB = headB.next;
                len--;
            }
        }
        //注意！！ 值相等不代表节点相等
        while(headA != null ){
            if(headA== headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

• Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
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

文章：8. 环形链表II

题目：142. 环形链表 II

【思路】

快慢指针，//找环的入口,head从头出发，和fast相遇的位置都是环的起点

• Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
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 {
            //return slow  说明确认是环
            //找环的入口,head从头出发，和fast相遇的位置都是环的起点
            for fast != head{
                fast = fast.Next
                head = head.Next
            }
            return head

        }
    }
    return nil
}

---

【算法总结】

• 两两交换链表中的节点：虚拟头结点会了，还不太熟练；递归法还不会
• 删除链表的倒数第N个节点：拉开N个身位后处理节点即可
• 链表相交：起点相同后比较节点是否相等
• 环形链表II：1确认环：快慢指针相等，2找到环入口：head指针从头出发，和fast相遇的点即环入口

链表总结篇

#链表的理论基础

在这篇文章关于链表，你该了解这些！ (opens new window)中，介绍了如下几点：

• 链表的种类主要为：单链表，双链表，循环链表
• 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
• 链表是如何进行增删改查的。
• 数组和链表在不同场景下的性能分析。

可以说把链表基础的知识都概括了，但又不像教科书那样的繁琐。

#链表经典题目

#虚拟头结点

在链表：听说用虚拟头节点会方便很多？ (opens new window)中，我们讲解了链表操作中一个非常总要的技巧：虚拟头节点。

链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

在链表：听说用虚拟头节点会方便很多？ (opens new window)中，我给出了用虚拟头结点和没用虚拟头结点的代码，大家对比一下就会发现，使用虚拟头结点的好处。

#链表的基本操作

在链表：一道题目考察了常见的五个操作！ (opens new window)中，我们通设计链表把链表常见的五个操作练习了一遍。

这是练习链表基础操作的非常好的一道题目，考察了：

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点的数值

可以说把这道题目做了，链表基本操作就OK了，再也不用担心链表增删改查整不明白了。

这里我依然使用了虚拟头结点的技巧，大家复习的时候，可以去看一下代码。

#反转链表

在链表：听说过两天反转链表又写不出来了？ (opens new window)中，讲解了如何反转链表。

因为反转链表的代码相对简单，有的同学可能直接背下来了，但一写还是容易出问题。

反转链表是面试中高频题目，很考察面试者对链表操作的熟练程度。

我在文章 (opens new window)中，给出了两种反转的方式，迭代法和递归法。

建议大家先学透迭代法，然后再看递归法，因为递归法比较绕，如果迭代还写不明白，递归基本也写不明白了。

可以先通过迭代法，彻底弄清楚链表反转的过程！

#删除倒数第N个节点

在链表：删除链表倒数第N个节点，怎么删？ (opens new window)中我们结合虚拟头结点 和 双指针法来移除链表倒数第N个节点。

#链表相交

链表：链表相交 (opens new window)使用双指针来找到两个链表的交点（引用完全相同，即：内存地址完全相同的交点）

#环形链表

在链表：环找到了，那入口呢？ (opens new window)中，讲解了在链表如何找环，以及如何找环的入口位置。

这道题目可以说是链表的比较难的题目了。 但代码却十分简洁，主要在于一些数学证明。