标签：面试题 ListNode cur head next 链表 dummyNode 节点

代码随想录

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

carl

链表 #dummyNode #双指针 #递归

思路

• 借助dummyNode简化判断条件
• 使用双指针更清晰一些，两个指针分别指向要交换的两节点的前一位置

细节

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyNode = new ListNode(0, head);
        ListNode* pre = dummyNode;
        ListNode* cur = head;
        while(cur && cur->next){
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = cur;
            pre->next = tmp;
            pre = cur;
            cur = cur->next;
        }
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

受反转链表递归方法启发，也可以用递归

• 递归函数的形参仍然设为双指针
• 由于使用了dummyNode，因此不需要在递归中更新head，所以不设返回值也可以，省了在递归函数中更新head的操作
• 在递归函数中完成操作
• 在调用自身时更新实参
  LeetCode 206. 反转链表 carl

class Solution {
public:
    void swapP(ListNode* pre, ListNode* cur){
        if(cur == nullptr || cur->next == nullptr){
            return;
        }
        ListNode* tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = cur;
        pre->next = tmp;
        swapP(cur, cur->next);
    }

    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyNode = new ListNode(0, head);
        swapP(dummyNode, head);
        head = dummyNode->next;
        return head;
    }

};

不使用双指针也容易实现
此处省略
递归法

class Solution {
public:
    ListNode* swapPairs(ListNode* head) { //---------------------递归的形参和返回值被确定
										  //传入要反转的链表头指针，返回完成后的头指针
        if(head == nullptr || head->next == nullptr){ //---------递归最深层
            return head;
        }
        ListNode* tmp = head->next; //---------------------------
        head->next = swapPairs(tmp->next); //--由于返回值是链表头指针，因此要在此处调用递归
									//---------使得递归的返回值能正确发挥作用
        tmp->next = head;
        return tmp;
    }
};

---

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

carl

链表 #dummyNode #双指针

思路

• 借助dummyNode简化判断条件
• 双指针简化思路

细节

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyNode = new ListNode(0, head);
        ListNode* pre = dummyNode;
        ListNode* cur = head;
        while(--n){
            cur = cur->next;
        }
        while(cur->next){
            cur = cur->next;
            pre = pre->next;
        }
        ListNode* tmp = pre->next;
        pre->next = tmp->next;
        delete tmp;
        head = dummyNode->next;
        delete dummyNode;
        return head;
    }
};

---

LeetCode 面试题 02.07. 链表相交

carl

链表 #链表相交

思路
方法一：

• 如果相交，则后半段路程相同。让二者走相同的路程，就会同时到达相交点
• LeetCode解法
  ![[Pasted image 20221015131529.png]]
  方法二：
• 先求长度差值，让链表末尾对齐，代码复杂些，但更容易想到

---

LeetCode 142. 环形链表 II

carl

链表 #环形链表 #双指针

思路

• 快慢指针相对移动1个节点，避免跳过
• 追及相遇问题的简单数学关系

细节

• LeetCode循环条件写得太冗余，不如随想录

![[Pasted image 20221015135438.png]]
![[Pasted image 20221015162900.png]]

标签：面试题,ListNode,cur,head,next,链表,dummyNode,节点
From： https://www.cnblogs.com/nsf1010/p/16794535.html