代码随想录LeetCode | 链表刷题总结II

前沿：撰写博客的目的是为了再刷时回顾和进一步完善，其次才是以教为学，所以如果有些博客写的较简陋，是为了保持进度不得已而为之，还请大家多多见谅。

预：看到题目后的思路和实现的代码。

见：参考答案展示。

感思：对比答案后的思考，与之前做过的题目是否有关联。

行：

（1）对于没做出来的题目，阅读答案后重新做一遍；

（2）下次做题可以尝试改善的方向；

（3）有助于理解的相关的题目

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

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

输入：head = [1,2,3,4]
输出：[2,1,4,3]

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

预

一刷时在画布上乱花半小时，始终没有写出答案，二刷能够画出来了，有进步！

推荐在线画布：Excalidraw | Hand-drawn look & feel • Collaborative • SecureExcalidraw | Hand-drawn look & feel • Collaborative • SecureExcalidraw | Hand-drawn look & feel • Collaborative • Secure

class Solution {
    //17min
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
       ListNode dummyNode = new ListNode();
       dummyNode.next = head;
       ListNode pre = dummyNode;
       ListNode cur = head;
       ListNode next = cur.next;
       while(next != null){
           pre.next = next;
           cur.next = next.next;
           next.next = cur;
           if(cur.next != null && cur.next.next != null){
            pre = cur;
            cur = cur.next;
            next = cur.next;
           }else{
               next = null;
           }
       }
       return dummyNode.next;
    }
}

感思

解题思路：

1.获得想要修改的节点的前节点才能修改（画图确定修改顺序）

2.分奇偶两种情况，判断条件：cur.next != null && cur.next.next !=null

常见错误：空指针or无限循环

画图确定修改顺序：

可行性分析：每次修改next后要删掉原来的指向，可尝试调换顺序来是否可行。

  

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

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

预

解题思路：

看到倒数第N个节点，就想到使用快慢指针产生间距N。

只要fast遍历到头，slow即是倒数第N个节点。

// Java代码
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode fast = head;
        ListNode slow = dummyNode;
        for(int i = 1;i < n;i++){
            fast = fast.next;
        }
        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

见：递归版本有空再实现

// 参考答案：递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
 
        return next;
    }
} 

3.链表相交

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

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

预见

大体思路一致，但直接判断值相等，导致共同链前面巧合相同这种情况无法判断。

就像例子中会直接将3作为相交节点。

感思

解题思路：相交后必全部相同

1.分别通过while循环，获得两个ListNode的长度Alen,Blen=5,6;

2.长的链表遍历到与短的链表长度相同

3.存储此时经过处理后长度相同的一个链表，命名为temp

4.while循环判断链表是否相同，而不是判断值相等。

// Java代码
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // System.out.println(0);
        if(headA == null || headB == null){
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        // 1.分别通过while循环，获得两个ListNode的长度Alen,Blen=5,6;
        int Alen = 0;
        int Blen = 0;
        while(curA != null){
            curA = curA.next;
            Alen++;
        }
        while(curB != null){
            curB = curB.next;
            Blen++;
        }
        // 2.长的链表遍历到与短的链表长度相同
        curA = headA;
        curB = headB;
        int index = 0;
        if(Alen > Blen){
            for(int i = 0;i < (Alen-Blen);i++){
                curA = curA.next;
            }
        }else{
            for(int i = 0;i < (Blen-Alen);i++){
                curB = curB.next;
            }
        }
        // 3.存储此时经过处理后长度相同的一个链表，命名为temp
        // 4.while循环判断是否存在后半段一直相同的情况，并记录后半段一直相同的长度。
        ListNode temp = curA;
        while(curA != null){
                if(curA == curB){
                    return curA;
                }
                curA = curA.next;
                curB = curB.next;
            }
        return null;
    }
}

1.环形链表 II

题目链接：142. 环形链表 II

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

做题思路

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //快慢指针判断有环+数学推导从头遍历获得入环节点；
        if(head == null || head.next == null) return null; //head为空肯定不是环
        //fast的步频是slow的两倍，所以第一步应该直接等于head.next.next，所以先前要先判断是否能够赋值，即判断head.next是否为空；
        //fast和slow的初始化为第一步，便于后面直接写while循环判断，不考虑如何开始（fast != slow）
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        //判断是否为环
        while(fast != null && fast.next != null && fast != slow){
            fast = fast.next.next;
            slow = slow.next;
        }
        //为空肯定不是环,排除为空导致出的while循环；
        if(fast == null || fast.next == null){
            return null;
        }
        //数学推导公式具体看图
        while(head != slow){
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}

 刷题回顾