LeetCode 1721: Swapping Nodes in a Linked List

Problem Statement :

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 :

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

Solution:

Our main task is to determine the locations of the nodes whose values are to be swapped.

We are going to take a 2-pointer approach to solve this problem, what we have to keep in mind is that we have to maintain the gap between these two pointers.

The distance should be chosen such that:

• when slow is at the head, fast points at the first node for swapping
• when fast is at the end, slow points at the second node for swapping

So, by following this approach we can solve this problem in O(n) time and O(1) space.

Implementation:

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode first=head,second=head,fast=head,slow=head;        
        while(k!=1){
            fast = fast.next;
            k--;
        }
        first = fast;
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        second = slow;
        k = slow.val;
        slow.val = first.val;
        first.val = k;
        return head;
    }
}

References:
- Leetcode Discussion

To connect and collaborate ping me:
LinkedIn
Twitter
GitHub