Swapping Nodes in a Linked List

MEDIUM

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

Approaches

Checkout 3 different approaches to solve Swapping Nodes in a Linked List. Click on different approaches to view the approach and algorithm in detail.

Convert to Array and Swap

This approach involves converting the linked list into an array (or a List in Java). Once the list is in an array format, we can use indices to directly access the k-th element from the beginning and the k-th element from the end. After swapping their values, the original linked list, whose nodes are stored in the array, is modified.

Algorithm

Create a java.util.ArrayList to store the nodes of the linked list.
Iterate through the linked list from the head, adding each ListNode to the ArrayList.
Let n be the size of the ArrayList. The k-th node from the beginning is at index k-1.
The k-th node from the end is at index n-k.
Retrieve the two nodes: node1 = list.get(k-1) and node2 = list.get(n-k).
Swap the val fields of node1 and node2.
Return the original head of the list.

The core idea is to trade space for simplicity. By traversing the linked list once and storing all its nodes in a dynamic array like ArrayList, we can leverage random access capabilities. The k-th node from the start is simply the element at index k-1, and the k-th node from the end is at index n-k (where n is the total number of nodes). After getting references to these two nodes, we can swap their values directly.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.ArrayList;
import java.util.List;

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            nodes.add(current);
            current = current.next;
        }

        int n = nodes.size();
        ListNode node1 = nodes.get(k - 1);
        ListNode node2 = nodes.get(n - k);

        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;

        return head;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once to populate the array, which takes O(n) time. Accessing elements in the `ArrayList` by index takes O(1) time.Space Complexity: O(n), as we need an auxiliary `ArrayList` to store all the n nodes of the linked list.

Pros and Cons

Pros:

Simple to understand and implement.
Direct access to nodes once they are in an array makes finding the target nodes trivial.

Cons:

High space complexity, which can be an issue for very large lists.
Less efficient than in-place algorithms that do not require extra data structures.

Code Solutions

Checking out 4 solutions in different languages for Swapping Nodes in a Linked List. Click on different languages to view the code.

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode SwapNodes ( ListNode head , int k ) { ListNode fast = head ; while (-- k > 0 ) { fast = fast . next ; } ListNode p = fast ; ListNode slow = head ; while ( fast . next != null ) { fast = fast . next ; slow = slow . next ; } ListNode q = slow ; int t = p . val ; p . val = q . val ; q . val = t ; return head ; } }

Video Solution

Watch the video walkthrough for Swapping Nodes in a Linked List

Patterns:

Two Pointers

Data Structures:

Linked List

Companies:

Nvidia |Snowflake |