Problem

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).

OR

Given a Linked List and a number k, Swap Kth Node from the front with the Kth Node from the End

Examples

Example 1:

---
title: Input List and k = 2
---

 graph LR
   A1[1] --> B2[2]:::kth_node --> C3[3] --> D4[4] --> E5[5]
   classDef kth_node fill:#1E90FF,stroke:#000,stroke-width:2px;
  
---
title: Output List
---
 graph LR
   A1[1] --> D4[4]:::kth_node --> C3[3] --> B2[2]:::kth_node --> E5[5]
   classDef kth_node fill:#1E90FF,stroke:#000,stroke-width:2px;
  
1
2

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

Example 2:

---
title: Input List and k = 5
---

 graph LR
   A7[7] --> B9[9] --> C6[6] --> D6[6] --> E7[7]:::kth_node --> F8[8] --> G3[3] --> H0[0] --> I9[9] --> J5[5]
   classDef kth_node fill:#1E90FF,stroke:#000,stroke-width:2px;
  
---
title: Output List
---

 graph LR
   A7[7] --> B9[9] --> C6[6] --> D6[6] --> F8[8]:::kth_node --> E7[7]:::kth_node --> G3[3] --> H0[0] --> I9[9] --> J5[5]
   classDef kth_node fill:#1E90FF,stroke:#000,stroke-width:2px;
  
1
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]

Solution

Method 1 - Find the length of list

  • Determine Length of the List: Traverse the list to determine its total length n.
  • Identify k-th Nodes:
    • The k-th node from the beginning is straightforward.
    • The k-th node from the end is the (n - k + 1)-th node from the beginning.
  • Swap Values: Swap the values of the identified nodes.
  • Return the Modified List: Return the head of the modified linked list.

Code

 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

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // Step 1: Determine the length of the list
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        // Step 2: Identify the kth node from the beginning and the end
        ListNode kthFromBeg = head;
        for (int i = 0; i < k - 1; i++) {
            kthFromBeg = kthFromBeg.next;
        }

        ListNode kthFromEnd = head;
        for (int i = 0; i < length - k; i++) {
            kthFromEnd = kthFromEnd.next;
        }

        // Step 3: Swap the values of the kth node from the beginning and the
        // end
        int temp = kthFromBeg.val;
        kthFromBeg.val = kthFromEnd.val;
        kthFromEnd.val = temp;

        // Step 4: Return the head of the modified list
        return head;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        # Step 1: Determine the length of the list
        length = 0
        current = head
        while current:
            length += 1
            current = current.next

        # Step 2: Identify the kth node from the beginning and the end
        kth_from_beg = head
        for _ in range(k - 1):
            kth_from_beg = kth_from_beg.next

        kth_from_end = head
        for _ in range(length - k):
            kth_from_end = kth_from_end.next

        # Step 3: Swap the values of the kth node from the beginning and the end
        kth_from_beg.val, kth_from_end.val = kth_from_end.val, kth_from_beg.val

        # Step 4: Return the head of the modified list
        return head

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the linked list. We traverse the list multiple times, but each traversal is linear with respect to the number of nodes.
  • 🧺 Space complexity: O(1), as we are using a constant amount of extra space for pointers and variables.