Description

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:

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

Example 2:

1Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
2Output: [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

Solution

Two Pass

One possible option is to iterate through the list and find the length of the list. Now, move the first node to k positions from the head. For second node, we have to find it from the end, which is equivalent to length - k + 1 node from the beginning. Once both nodes are found, simply swap those two using additional temporary ListNode. This solution although has time complexity O(n), it requires two pass through the list.

 1class Solution {
 2    public ListNode swapNodes(ListNode head, int k) {
 3        if (head == null) {
 4            return null;
 5        }
 6        ListNode current = head;
 7        int length = 0;
 8        while (current != null) {
 9            length++;
10            current = current.next;
11        }
12        ListNode first = head;
13        ListNode second = head;
14        for (int i = 1; i < k; i++) {
15            first = first.next;
16        }
17//        System.out.println("first: " + first.val);
18        for (int i = 1; i < length - k + 1; i++) {
19            second = second.next;
20        }
21//        System.out.println("second: " + second.val);
22        int temp = first.val;
23        first.val = second.val;
24        second.val = temp;
25        return head;
26    }
27}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Better Approach - Single Pass

In this case we can use the same technique to find the kth node from the end using two pointers offset by k positions. In the code below, we iterate through the list using current pointer and also track size variable. When the size = k then we have found our firstNode. At this point, we can initialize our secondNode to head so that it’s offset by k. Now, when current eventually reaches end of the list, the secondNode will be at size - k position, that is kth from the end. Now that we have found the two nodes to swap, we simply swap them using a temp node.

 1class Solution {
 2    public ListNode swapNodes2 (ListNode head, int k) {
 3        if (head == null) {
 4            return null;
 5        }
 6        ListNode current = head, firstNode = null, secondNode = null;
 7        int length = 0;
 8        while (current != null) {
 9            length++;
10            if (secondNode != null) {
11                secondNode = secondNode.next;
12            }
13            if (length == k) {
14                firstNode = current;
15                secondNode = head;
16            }
17            current = current.next;
18        }
19        int temp = firstNode.val;
20        firstNode.val = secondNode.val;
21        secondNode.val = temp;
22        return head;
23    }
24}
  • Time Complexity: O(n)
  • Space Complexity: O(1)