2026/02/24

[LeetCode] 1721 Swapping Nodes in a Linked List

要自己做dummy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* getBeginKthNode(ListNode* head, int k) {
    ListNode* node = head;
    for (int i = 0; i < k; i++)
      node = node->next;
    return node;
  }

  ListNode* getEndKthNode(ListNode* head, int k) {
    ListNode* fastNode = getBeginKthNode(head, k);
    ListNode* slowNode = head;

    while (fastNode != nullptr) {
      slowNode = slowNode->next;
      fastNode = fastNode->next;
    }

    return slowNode;
  }

  ListNode* swapNodes(ListNode* head, int k) {
    ListNode* DUMMY = new ListNode(5566, head);
    ListNode* beginKthNode = getBeginKthNode(DUMMY, k);
    ListNode* endKthNode = getEndKthNode(DUMMY, k);
    swap(beginKthNode->val, endKthNode->val);
    return head;
  }
};
Labels: