We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Swapping Nodes in a Linked List

Number: 528

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta

Problem Description

Given the head of a linked list and an integer k, swap the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed). Return the head of the modified list.

Key Insights

  • Use a two-pointer technique to identify the kth node from the beginning and the kth node from the end.
  • First, traverse the list to reach the kth node from the beginning.
  • Then, use a pointer starting at the kth node and a second pointer starting at the head to reach the kth node from the end by moving them until the first pointer reaches the end.
  • Swap the values of the two identified nodes.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution uses the two-pointer approach to efficiently locate the two nodes whose values need to be swapped. First, traverse from the head and stop at the kth node (this is the kth node from the beginning). Save a reference to this node. Next, start a new pointer at the head and simultaneously traverse from the kth node to the end of the list. When the latter pointer reaches the end, the pointer started at the head will be at the kth node from the end. Finally, swap the values of these two nodes. The swap is done in place without altering the list structure, which ensures an O(1) space complexity.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        # Step 1: Find the kth node from the beginning
        kth_from_begin = head
        for _ in range(k - 1):
            kth_from_begin = kth_from_begin.next
        
        # Save the reference to kth node from beginning
        first_node = kth_from_begin
        
        # Step 2: Use two pointers to find kth node from the end
        kth_from_end = head
        current = kth_from_begin
        while current.next:
            kth_from_end = kth_from_end.next
            current = current.next
        
        # Step 3: Swap the values of the two nodes
        first_node.val, kth_from_end.val = kth_from_end.val, first_node.val
        
        # Return the modified list head
        return head
← Back to All Questions