# Swapping Nodes in a Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/swapping-nodes-in-a-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/swapping-nodes-in-a-linked-list
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Linked List
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia), [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## 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**)._

**Example 1:**

![](https://assets.glich.co/dsa/swapping-nodes-in-a-linked-list/image0.jpg) 

**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 <= 105`
* `0 <= Node.val <= 100`

# Approaches
## 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.
**Time:** 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:** O(n), as we need an auxiliary `ArrayList` to store all the n nodes of the linked list.
**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.
### Explanation
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.

```java
/**
 * 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;
    }
}
```
### 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.

## Two-Pass Algorithm
This approach avoids using extra space by traversing the list multiple times. First, we find the total length of the list. With the length, we can calculate the position of the k-th node from the end. Then, we traverse the list again to find both the k-th node from the beginning and the k-th node from the end and swap their values.
**Time:** O(n), where n is the number of nodes. The list is traversed once to find the length (O(n)), and then up to two more times to find the nodes (O(k) and O(n-k)). The total time complexity is O(n) + O(k) + O(n-k) = O(2n) which simplifies to O(n). · **Space:** O(1), as we only use a few pointers and variables to keep track of the nodes and length, regardless of the list size.
**Pros:** Space efficient, using constant extra space.; Relatively easy to reason about and implement correctly.
**Cons:** Requires multiple passes over the linked list, which is less efficient than a single-pass solution in terms of total operations.
### Explanation
This method is space-efficient. The first pass is dedicated to calculating the total number of nodes, `n`. Knowing `n`, the position of the k-th node from the end can be determined as `n - k + 1` from the beginning. With the positions of both nodes known, we perform two more traversals from the head of the list to locate each node. The first traversal goes `k-1` steps to find the first node, and the second traversal goes `n-k` steps to find the second node. Finally, we swap their values.

```java
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // Pass 1: Find the length of the list
        int n = 0;
        ListNode current = head;
        while (current != null) {
            n++;
            current = current.next;
        }

        // Find the first node (k-th from beginning)
        ListNode node1 = head;
        for (int i = 0; i < k - 1; i++) {
            node1 = node1.next;
        }

        // Find the second node (k-th from end, which is n-k+1 from beginning)
        ListNode node2 = head;
        for (int i = 0; i < n - k; i++) {
            node2 = node2.next;
        }

        // Swap the values
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;

        return head;
    }
}
```
### Algorithm
- First, traverse the list to find its length, `n`.
- The k-th node from the beginning is found by traversing `k-1` steps from the `head`. Let's call this `node1`.
- The k-th node from the end is the `(n - k + 1)`-th node from the beginning. We can find this node by traversing `n-k` steps from the `head`. Let's call this `node2`.
- Once both `node1` and `node2` are found, swap their values.
- Return the original `head`.

## One-Pass Algorithm with Pointers
This is the most optimal approach. It finds both nodes in a single pass using pointers. We first advance one pointer `k-1` steps to locate the k-th node from the beginning. Then, we start a second pointer from the head and advance both pointers together until the first pointer reaches the end of the list. At this point, the second pointer will be at the k-th node from the end.
**Time:** O(n), where n is the number of nodes. We traverse the list only once. The first loop runs `k-1` times, and the second loop runs `n-k` times. The total number of steps is `(k-1) + (n-k) = n-1`, which constitutes a single pass. · **Space:** O(1). We only use a constant number of pointers, regardless of the list size.
**Pros:** Most efficient in terms of both time and space.; Traverses the list only once, minimizing the number of node visits.
**Cons:** The logic with two pointers moving at different stages might be slightly more complex to grasp initially compared to the two-pass approach.
### Explanation
This elegant solution uses the two-pointer technique to solve the problem in a single pass. We first identify the k-th node from the beginning. Let's call it `node1`. We use a pointer, say `current`, and advance it `k-1` times from the head. Now, `current` is at `node1`. To find the k-th node from the end, we use another pointer, `node2`, initialized at the head. We then continue to advance `current` to the end of the list. For every step `current` takes, we also advance `node2`. The gap between `node2` and the end of the list will be the same as the gap between the head and `node1`'s initial position. Thus, when `current` reaches the last node, `node2` will be at the k-th position from the end.

```java
/**
 * 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; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode current = head;
        // Move current k-1 steps to find the k-th node from the beginning
        for (int i = 0; i < k - 1; i++) {
            current = current.next;
        }
        
        // This is the first node to be swapped
        ListNode node1 = current;
        
        // This will be the second node to be swapped, start it from the head
        ListNode node2 = head;
        
        // Move current to the end of the list.
        // As current moves, move node2. This maintains a gap of n-k between them.
        // When current reaches the end, node2 will be at the k-th position from the end.
        while (current.next != null) {
            current = current.next;
            node2 = node2.next;
        }
        
        // Swap the values
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
        
        return head;
    }
}
```
### Algorithm
- Initialize a `current` pointer to `head`. Also initialize two pointers, `node1` and `node2`, which will eventually point to the nodes to be swapped.
- First, find the k-th node from the beginning. Move the `current` pointer `k-1` steps forward.
- After the loop, `current` points to the k-th node. Assign this node to `node1`.
- Now, `node1` is found. To find `node2` (the k-th node from the end), initialize `node2` to `head`.
- Continue traversing with `current` from its current position until it reaches the end of the list. Simultaneously, move `node2` forward from the head.
- When `current` reaches the last node, `node2` will be pointing to the k-th node from the end.
- Swap the values of `node1` and `node2`.
- Return `head`.

# Solutions
### CSharp

```csharp
/** * 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 ; } }
```

### Java

```java
/** * 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; } * } */ 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 ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * swapNodes ( ListNode * head , int k ) { ListNode * fast = head ; while ( -- k ) { fast = fast -> next ; } ListNode * slow = head ; ListNode * p = fast ; while ( fast -> next ) { fast = fast -> next ; slow = slow -> next ; } ListNode * q = slow ; swap ( p -> val , q -> val ); return head ; } };
```

### Python

```python
# 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 : Optional [ ListNode ], k : int ) -> Optional [ ListNode ]: fast = slow = head for _ in range ( k - 1 ): fast = fast . next p = fast while fast . next : fast , slow = fast . next , slow . next q = slow p . val , q . val = q . val , p . val return head
```