交换节点

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100

思路

设置虚拟头节点，然后两两交换

Complexity

  • Time complexity: O(n)
  • Space complexity: O(1)

C++解法

/**
 * 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* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        ListNode* cur = head;
        while(cur != NULL && cur->next != NULL){
            ListNode* temp = cur->next->next;
            cur->next->next = cur;
            pre->next = cur->next;
            cur->next = temp;
            pre = cur;
            cur = temp;
        }
        return dummyHead->next;
    }
};

Java解法

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy, cur = head;

        while (cur != null && cur.next != null) {
            ListNode npn = cur.next.next;
            ListNode second = cur.next;

            second.next = cur;
            cur.next = npn;
            prev.next = second;

            prev = cur;
            cur = npn;
        }

        return dummy.next;        
    }
}

Python3解法

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev, cur = dummy, head

        while cur and cur.next:
            npn = cur.next.next
            second = cur.next

            second.next = cur
            cur.next = npn
            prev.next = second

            prev = cur
            cur = npn
        
        return dummy.next

1721. Swapping Nodes in a Linked List

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 10^5
  • 0 <= Node.val <= 100

思路

方法一：

We can traverse the linked list and store the elements in an array.

Upon conversion to an array, we can swap the required elements by indexing the array.

We can rebuild the linked list using the order of the elements in the array.

方法二：

  • To solve this problem in one pass, we can use a two-pointer approach.
  • First, we can initialize two pointers, left_ptr and right_ptr, both pointing to the head of the linked list. We can then move the right_ptr k-2 steps forward.
  • After this, we can move both left_ptr and right_ptr forward simultaneously until right_ptr reaches the end of the list.
  • At this point, left_ptr will be pointing to the kth node from the beginning, and end_ptr will be pointing to the kth node from the end.
  • We can then swap the values of these two nodes, and return the head of the linked list.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

C++解法

方法一：

/**
 * 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* swapNodes(ListNode* head, int k) {
        vector<int> nums;
        ListNode* cur = head;
        while(cur != NULL){
            nums.push_back(cur->val);
            cur = cur->next;
        }
        swap(nums[k-1], nums[nums.size()-k]);
        ListNode* dummyHead  = new ListNode(0);
        cur = dummyHead;
        for(int i = 0; i < nums.size(); i++){
            ListNode* newNode = new ListNode(nums[i]);
            cur->next = newNode;
            cur = newNode;
        }
        return dummyHead->next;
    }
};

方法二：

/**
 * 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* swapNodes(ListNode* head, int k) {
        ListNode* dummyHead  = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        for(int i = 0; i < k; i++){
            fast = fast->next;
        }
        ListNode* temp = fast;
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        swap(slow->val, temp->val);
        return dummyHead->next;
    }
};