1721.Swapping Nodes in a Linked List

tags: Medium,Linked List,Two Pointers

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 k^th node from the beginning and the k^th 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⁵
• 0 <= Node.val <= 100

解答

Python

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        L = head
        for i in range(1, k):
            L = L.next
        R = head
        cur = L
        while cur.next:
            cur = cur.next
            R = R.next
        L.val, R.val = R.val, L.val
        return head

Yen-Chi ChenMon, May 15, 2023

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 1
        current = head

        while current.next:
            n += 1
            current = current.next

        current = head
        target1, target2 = ListNode(), ListNode()
        
        for i in range(1, n + 1):
            if i == k:
                target1 = current
            if i == n - k + 1:
                target2 = current

            current = current.next

        target1.val, target2.val = target2.val, target1.val

        return head

Ron ChenMon, May 15, 2023

Javascript

function swapNodes(head, k) {
  let slow = head;
  let fast = head;

  for (let i = 1; i < k; i++) {
    fast = fast.next;
  }

  let first = fast;

  // 第一個要交換的node到底的距離等於head到第二個要交換的node的距離
  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }

  let second = slow;

  const temp = first.val;
  first.val = second.val;
  second.val = temp;

  return head;
}

MarsgoatMon, May 15, 2023

Reference

回到題目列表