Two Pointer Techniques for Linked List Problems

This article summarizes basic techniques for singly linked lists, with each technique corresponding to at least one algorithm problem:

1. Merging Two Sorted Linked Lists
2. Splitting a Linked List
3. Merging k Sorted Linked Lists
4. Finding the k-th Node from the End of a Singly Linked List
5. Finding the Middle Node of a Singly Linked List
6. Detecting a Cycle in a Singly Linked List and Finding the Start of the Cycle
7. Determining if Two Singly Linked Lists Intersect and Finding the Intersection Node

These solutions all use the double pointer technique, which is very widely used for singly linked list problems. Let's go through them one by one.

Merging Two Sorted Linked Lists

This is the most basic linked list technique. LeetCode problem 21, "Merge Two Sorted Linked Lists," addresses this issue. You are given two sorted linked lists and asked to merge them into a new sorted linked list:

21. Merge Two Sorted Lists | LeetCode |

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

// The function signature is as follows
ListNode mergeTwoLists(ListNode l1, ListNode l2);

// The function signature is as follows
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2);

# The function signature is as follows
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:

// The function signature is as follows
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {}

// the function signature is as follows
var mergeTwoLists = function(l1, l2) {}

This problem is quite simple. Let's directly look at the solution:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // virtual head node
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;
        
        while (p1 != null && p2 != null) {

            // compare pointers p1 and p2
            // attach the node with the smaller value to the p pointer
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // advance the p pointer
            p = p.next;
        }
        
        if (p1 != null) {
            p.next = p1;
        }
        
        if (p2 != null) {
            p.next = p2;
        }
        
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // dummy head node
        ListNode dummy(-1), *p = &dummy;
        ListNode *p1 = l1, *p2 = l2;
        
        while (p1 != nullptr && p2 != nullptr) {

            // compare the two pointers p1 and p2
            // attach the node with the smaller value to the pointer p
            if (p1->val > p2->val) {
                p->next = p2;
                p2 = p2->next;
            } else {
                p->next = p1;
                p1 = p1->next;
            }
            // advance the pointer p continuously
            p = p->next;
        }
        
        if (p1 != nullptr) {
            p->next = p1;
        }
        
        if (p2 != nullptr) {
            p->next = p2;
        }
        
        return dummy.next;
    }
};

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # dummy head node
        dummy = ListNode(-1)
        p = dummy
        p1 = l1
        p2 = l2
        
        while p1 is not None and p2 is not None: 

            # compare the two pointers p1 and p2
            # attach the node with the smaller value to the p pointer
            if p1.val > p2.val:
                p.next = p2
                p2 = p2.next
            else:
                p.next = p1
                p1 = p1.next
            # the p pointer keeps moving forward
            p = p.next
        
        if p1 is not None:
            p.next = p1
        
        if p2 is not None:
            p.next = p2
        
        return dummy.next

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // dummy head node
    dummy := &ListNode{-1, nil}
    p := dummy
    p1 := l1
    p2 := l2
    
    for p1 != nil && p2 != nil {

        // compare pointers p1 and p2
        // attach the node with the smaller value to the p pointer
        if p1.Val > p2.Val {
            p.Next = p2
            p2 = p2.Next
        } else {
            p.Next = p1
            p1 = p1.Next
        }
        // advance the p pointer
        p = p.Next
    }
    
    if p1 != nil {
        p.Next = p1
    }
    
    if p2 != nil {
        p.Next = p2
    }
    
    return dummy.Next
}

var mergeTwoLists = function(l1, l2) {
    // virtual head node
    var dummy = new ListNode(-1), p = dummy;
    var p1 = l1, p2 = l2;
    
    while (p1 !== null && p2 !== null) {

        // compare the two pointers p1 and p2
        // attach the node with the smaller value to the pointer p
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // the p pointer keeps moving forward
        p = p.next;
    }
    
    if (p1 !== null) {
        p.next = p1;
    }
    
    if (p2 !== null) {
        p.next = p2;
    }
    
    return dummy.next;
};

In our while loop, we compare the sizes of p1 and p2 each time, attaching the smaller node to the result list. Refer to the GIF below:

To visually understand, the logic of this algorithm is similar to zipping up a zipper, where l1 and l2 are like the teeth on either side of the zipper, and the pointer p acts like the slider, merging the two sorted linked lists. Alternatively, you can think of this process like protein synthesis, where l1 and l2 resemble amino acids, and the pointer p functions like the enzyme, linking the amino acids into proteins.

The code also employs a common technique in linked list problems known as the "dummy head node" or dummy node. You can test it out; without using a dummy node, the code becomes more complex, requiring extra handling for when pointer p is null. The dummy node serves as a placeholder, simplifying the code by avoiding null pointer scenarios.

Decomposing a Singly Linked List

Let's directly look at LeetCode Problem 86 "Partition List":

86. Partition List | LeetCode |

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

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

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].
• -100 <= Node.val <= 100
• -200 <= x <= 200

When merging two sorted linked lists, you combine them into one. Here, you need to decompose the original list into two. Specifically, we can split the original list into two smaller lists, with one containing elements less than x, and the other containing elements greater than or equal to x. Finally, by connecting these two lists together, you achieve the desired outcome.

The overall logic is very similar to merging sorted linked lists. Let's look at the code for details, and pay attention to the use of the dummy head node:

class Solution {
    public ListNode partition(ListNode head, int x) {
        // dummy head node for the list containing nodes less than x
        ListNode dummy1 = new ListNode(-1);
        // dummy head node for the list containing nodes greater than or equal to x
        ListNode dummy2 = new ListNode(-1);
        // p1, p2 pointers are responsible for creating the result list
        ListNode p1 = dummy1, p2 = dummy2;
        // p is responsible for traversing the original
        // list, similar to the logic of merging two
        // here we are splitting one list into two lists
        ListNode p = head;
        while (p != null) {
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.next = p;
                p1 = p1.next;
            }
            // we cannot move p pointer directly,
            // p = p.next
            // disconnect the next pointer of each node in the original list
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        // connect the two lists
        p1.next = dummy2.next;

        return dummy1.next;
    }
}

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // virtual head node for the list storing nodes less than x
        ListNode* dummy1 = new ListNode(-1);
        // virtual head node for the list storing nodes greater than or equal to x
        ListNode* dummy2 = new ListNode(-1);
        // p1, p2 pointers responsible for generating the result list
        ListNode* p1 = dummy1, *p2 = dummy2;
        // p is responsible for traversing the original
        // list, similar to the logic of merging two
        // here we decompose a list into two lists
        ListNode* p = head;
        while (p != nullptr) {
            if (p->val >= x) {
                p2->next = p;
                p2 = p2->next;
            } else {
                p1->next = p;
                p1 = p1->next;
            }
            // cannot directly advance the p pointer,
            // p = p->next
            // disconnect the next pointer of each node in the original list
            ListNode* temp = p->next;
            p->next = nullptr;
            p = temp;
        }
        // connect the two lists
        p1->next = dummy2->next;

        return dummy1->next;
    }
};

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # virtual head node for the list containing elements less than x
        dummy1 = ListNode(-1)
        # virtual head node for the list containing elements greater than or equal to x
        dummy2 = ListNode(-1)
        # p1, p2 pointers are responsible for creating the resulting list
        p1, p2 = dummy1, dummy2
        # p is responsible for traversing the original
        # list, similar to the logic of merging two
        # here we decompose one list into two lists
        p = head
        while p:
            if p.val >= x:
                p2.next = p
                p2 = p2.next
            else:
                p1.next = p
                p1 = p1.next
            # cannot directly move the p pointer forward,
            # p = p.next
            # break the next pointer of each node in the original list
            temp = p.next
            p.next = None
            p = temp
        # connect the two lists
        p1.next = dummy2.next

        return dummy1.next

func partition(head *ListNode, x int) *ListNode {
	// virtual head node for the list storing nodes less than x
	dummy1 := &ListNode{-1, nil}
	// virtual head node for the list storing nodes greater than or equal to x
	dummy2 := &ListNode{-1, nil}
	// pointers p1 and p2 are responsible for generating the result list
	p1, p2 := dummy1, dummy2
	// pointer p is responsible for traversing the
// original list, similar to merging two sorted
	// here we split one list into two lists
	p := head
	for p != nil {
		if p.Val >= x {
			p2.Next = p
			p2 = p2.Next
		} else {
			p1.Next = p
			p1 = p1.Next
		}
		// cannot move the p pointer forward directly,
		// p = p.Next
		// break the next pointer of each node in the original list
		temp := p.Next
		p.Next = nil
		p = temp
	}
	// connect the two lists
	p1.Next = dummy2.Next

	return dummy1.Next
}

var partition = function(head, x) {
    // dummy head node for the list with nodes less than x
    let dummy1 = new ListNode(-1);
    // dummy head node for the list with nodes greater than or equal to x
    let dummy2 = new ListNode(-1);
    // p1 and p2 pointers are responsible for creating the result lists
    let p1 = dummy1, p2 = dummy2;
    // p is responsible for traversing the original
    // list, similar to the logic of merging two sorted
    // here we split the list into two lists
    let p = head;
    while (p !== null) {
        if (p.val >= x) {
            p2.next = p;
            p2 = p2.next;
        } else {
            p1.next = p;
            p1 = p1.next;
        }
        // cannot directly advance the p pointer,
        // p = p.next
        // break the next pointer of each node in the original list
        let temp = p.next;
        p.next = null;
        p = temp;
    }
    // connect the two lists
    p1.next = dummy2.next;

    return dummy1.next;
};

I know many readers might have questions about this piece of code:

// Can't move the p pointer forward directly,
// p = p.next
// Break the next pointer of each node in the original linked list
ListNode temp = p.next;
p.next = null;
p = temp;

Let's get straight to the point with our visual panel to understand it better. First, here's the correct way to do it:

If you don't disconnect the next pointer of each node in the original linked list, an error will occur because the resulting linked list will contain a cycle:

In general, if we need to attach nodes from the original linked list to a new linked list instead of creating new nodes, it might be necessary to disconnect the links between the nodes and the original list. This can be a good habit to develop: whenever you encounter such a situation, break the connection of the original linked list nodes to avoid errors.

Merging k Sorted Linked Lists

Let's look at LeetCode Problem 23 "Merge k Sorted Lists":

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Input: lists = []
Output: []

Input: lists = [[]]
Output: []

// The function signature is as follows
ListNode mergeKLists(ListNode[] lists);

// The function signature is as follows
ListNode* mergeKLists(vector<ListNode*>& lists);

# The function signature is as follows
def mergeKLists(lists: List[ListNode]) -> ListNode:

// The function signature is as follows
func mergeKLists(lists []*ListNode) *ListNode

// The function signature is as follows
var mergeKLists = function(lists) {};

Merging k sorted linked lists is similar to merging two sorted linked lists. The challenge is how to quickly get the smallest node among the k nodes and attach it to the result linked list.

Here, we need to use a priority queue data structure. By putting the linked list nodes into a min-heap, we can get the smallest node among the k nodes each time. For more details on priority queues, you can refer to Priority Queue (Binary Heap) Principles and Implementation. This article will not go into that.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // virtual head node
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // priority queue, min-heap
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val));
        // add the head nodes of the k linked lists to the min-heap
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        while (!pq.isEmpty()) {
            // get the smallest node and attach it to the result linked list
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p pointer keeps moving forward
            p = p.next;
        }
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        // dummy head node
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        // priority queue, min-heap
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        // add the head nodes of k linked lists to the min-heap
        for (ListNode* head : lists) {
            if (head != nullptr) {
                pq.push(head);
            }
        }

        while (!pq.empty()) {
            // get the smallest node and attach it to the result linked list
            ListNode* node = pq.top();
            pq.pop();
            p->next = node;
            if (node->next != nullptr) {
                pq.push(node->next);
            }
            // move the p pointer forward continuously
            p = p->next;
        }
        return dummy->next;
    }
};

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    # Override comparison operators to facilitate adding ListNode to the min-heap
    def __lt__(self, other):
        return self.val < other.val

class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None
        # Dummy head node
        dummy = ListNode(-1)
        p = dummy
        # Priority queue, min-heap
        pq = []
        # Add the head nodes of k linked lists to the min-heap
        for i, head in enumerate(lists):
            if head is not None:
                heapq.heappush(pq, (head.val, i, head))

        while pq:
            # Get the smallest node and attach it to the result linked list
            val, i, node = heapq.heappop(pq)
            p.next = node
            if node.next is not None:
                heapq.heappush(pq, (node.next.val, i, node.next))
            # Move the p pointer forward continuously
            p = p.next
            
        return dummy.next

import "container/heap"

// Implement heap.Interface for ListNode
type PriorityQueue []*ListNode

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*ListNode))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    // dummy head node
    dummy := &ListNode{Val: -1}
    p := dummy

    // priority queue, min-heap
    pq := &PriorityQueue{}
    heap.Init(pq)

    // add the head nodes of the k linked lists to the min-heap
    for _, head := range lists {
        if head != nil {
            heap.Push(pq, head)
        }
    }

    for pq.Len() > 0 {
        // get the smallest node and attach it to the result linked list
        node := heap.Pop(pq).(*ListNode)
        p.Next = node
        if node.Next != nil {
            heap.Push(pq, node.Next)
        }
        // move the p pointer forward continuously
        p = p.Next
    }
    return dummy.Next
}

var mergeKLists = function(lists) {
    if (lists.length === 0) return null;

    // virtual head node
    var dummy = new ListNode(-1);
    var p = dummy;

    // priority queue, min heap
    var pq = new MinPriorityQueue({ priority: (node) => node.val });

    // add the head nodes of the k linked lists to the min heap
    for (var i = 0; i < lists.length; i++) {
        if (lists[i] !== null) {
            pq.enqueue(lists[i]);
        }
    }

    while (!pq.isEmpty()) {
        // get the smallest node and attach it to the result linked list
        var node = pq.dequeue().element;
        p.next = node;
        if (node.next !== null) {
            pq.enqueue(node.next);
        }
        // p pointer keeps moving forward
        p = p.next;
    }
    
    return dummy.next;
}

This algorithm is a common interview question. What is its time complexity?

The maximum number of elements in the priority queue pq is k, so the time complexity of a single poll or add operation is $O(\log k)$. All the linked list nodes will be added to and removed from pq, therefore, the overall time complexity of the algorithm is $O(N \log k)$, where k is the number of linked lists, and N is the total number of nodes in these linked lists.

The k-th Last Node in a Singly Linked List

Finding the k-th node from the start of a singly linked list is straightforward; you can simply use a for loop to traverse the list. But how do you find the k-th node from the end?

You might say, assuming the linked list has n nodes, the k-th last node is the (n - k + 1)-th node from the start, which can also be found with a for loop, right?

Yes, but typically, algorithm problems will only provide you with a ListNode head node representing a singly linked list. You cannot directly determine the length n of the list. You need to traverse the list once to calculate the value of n, and then traverse the list again to find the (n - k + 1)-th node.

This means that this solution requires traversing the list twice to find the k-th last node.

So, can we determine the k-th last node by traversing the list only once? Yes, it can be done. If this question is asked in an interview, the interviewer is likely expecting you to provide a solution that only requires a single traversal of the list.

This solution is quite clever. Assume k = 2, and the approach is as follows:

First, let a pointer p1 point to the head node head of the list, and then move k steps:

Now, p1 would need to move n - k more steps to reach the end of the list, right?

At this point, introduce another pointer p2 pointing to the head node head:

Next, it becomes clear. Move p1 and p2 forward simultaneously. When p1 reaches the end of the list, having moved n - k steps, p2 will also have moved n - k steps from head, stopping at the (n - k + 1)-th node, which is exactly the k-th last node of the list:

In this way, by traversing the list only once, you can obtain the k-th last node p2.

Below is the code for the above logic:

// return the k-th node from the end of the linked list
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 moves k steps first
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 and p2 move n - k steps together
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 is now pointing to the (n - k + 1)-th node, which is the k-th node from the end
    return p2;
}

// return the k-th node from the end of the linked list
ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    // p1 moves k steps first
    for (int i = 0; i < k; i++) {
        p1 = p1 -> next;
    }
    ListNode* p2 = head;
    // p1 and p2 move n - k steps together
    while (p1 != nullptr) {
        p2 = p2 -> next;
        p1 = p1 -> next;
    }
    // p2 now points to the (n - k + 1)-th node, which is the k-th node from the end
    return p2;
}

# return the k-th node from the end of the linked list
def findFromEnd(head: ListNode, k: int) -> ListNode:
    p1 = head
    # p1 goes k steps first
    for i in range(k):
        p1 = p1.next
    p2 = head
    # p1 and p2 go n - k steps together
    while p1 != None:
        p2 = p2.next
        p1 = p1.next
    # p2 now points to the (n - k + 1)-th node, which is the k-th node from the end
    return p2

// return the k-th node from the end of the linked list
func findFromEnd(head *ListNode, k int) *ListNode {
    p1 := head
    // p1 moves k steps forward
    for i := 0; i < k; i++ {
        p1 = p1.Next
    }
    p2 := head
    // p1 and p2 move n - k steps together
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    // p2 now points to the (n - k + 1)-th node, which is the k-th node from the end
    return p2
}

// return the k-th node from the end of the linked list
var findFromEnd = function(head, k) {
    var p1 = head;
    // p1 moves k steps first
    for (var i = 0; i < k; i++) {
        p1 = p1.next;
    }
    var p2 = head;
    // p1 and p2 move together n - k steps
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 now points to the (n - k + 1)-th node, which is the k-th node from the end
    return p2;
};

Of course, if we use Big O notation to calculate time complexity, the time complexity for traversing a linked list once or twice is both $O(N)$. However, the algorithm mentioned above is more skillful.

This technique is used in many linked list-related algorithm problems, such as LeetCode Problem 19 "Remove Nth Node From End of List":

19. Remove Nth Node From End of List | LeetCode |

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

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

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Let's directly look at the solution code:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // virtual head node
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // to remove the nth node from the end, first find the (n + 1)th node from the end
        ListNode x = findFromEnd(dummy, n + 1);
        // remove the nth node from the end
        x.next = x.next.next;
        return dummy.next;
    }
        
    private ListNode findFromEnd(ListNode head, int k) {
        // see the previous code
    }
}

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // dummy head node
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        // to delete the nth node from the end, first find the (n + 1)th node from the end
        ListNode* x = findFromEnd(dummy, n + 1);
        // delete the nth node from the end
        x->next = x->next->next;
        return dummy->next;
    }
    
private:
    ListNode* findFromEnd(ListNode* head, int k) {
        // code is shown above
    }
};

# main function
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # dummy head node
        dummy = ListNode(-1)
        dummy.next = head
        # to remove the nth from end, first find the (n + 1)th node from end
        x = self.findFromEnd(dummy, n + 1)
        # remove the nth node from end
        x.next = x.next.next
        return dummy.next
        
    def findFromEnd(self, head: ListNode, k: int) -> ListNode:
        # refer to the code above
        pass

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // virtual head node
    dummy := &ListNode{Val: -1}
    dummy.Next = head
    // to delete the nth node from the end, first find the (n+1)th node from the end
    x := findFromEnd(dummy, n+1)
    // delete the nth node from the end
    x.Next = x.Next.Next
    return dummy.Next
}

func findFromEnd(head *ListNode, k int) *ListNode {
    // code is shown above
}

// main function
var removeNthFromEnd = function(head, n) {
    // virtual head node
    let dummy = new ListNode(-1);
    dummy.next = head;
    // to remove the nth node from the end, first find the (n + 1)th node from the end
    let x = findFromEnd(dummy, n + 1);
    // remove the nth node from the end
    x.next = x.next.next;
    return dummy.next;
};

var findFromEnd = function(head, k) {
    // code is in the previous text
};

This logic is very simple. To delete the nth node from the end, you need to get a reference to the (n + 1)th node from the end, which can be done using our implemented findFromEnd function.

However, note that we also use a dummy head node to prevent null pointer issues. For example, if the list has 5 nodes and you need to delete the 5th node from the end (i.e., the first node), the algorithm should find the 6th node from the end. But there isn't a node before the first node, which would cause an error.

With the dummy node dummy, this issue is avoided, and the deletion can be handled correctly.

Middle of a Singly Linked List

LeetCode Problem 876 "Middle of the Linked List" addresses this topic. The key problem is that we cannot directly get the length n of the singly linked list. The conventional method is to first traverse the list to calculate n, and then traverse again to get the (n / 2)th node, which is the middle node.

If you want to find the middle node in a single traversal, you need to use a bit of cleverness by employing the "slow and fast pointers" technique:

We let two pointers, slow and fast, point to the head node of the list.

Each time the slow pointer slow advances one step, the fast pointer fast advances two steps. This way, when fast reaches the end of the list, slow will be pointing to the middle of the list.

The code implementation of the above idea is as follows:

class Solution {
    public ListNode middleNode(ListNode head) {
        // initialize slow and fast pointers to head
        ListNode slow = head, fast = head;
        // stop when fast pointer reaches the end
        while (fast != null && fast.next != null) {
            // slow pointer moves one step, fast pointer moves two steps
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow pointer points to the middle node
        return slow;
    }
}

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // initialize slow and fast pointers to head
        ListNode* slow = head;
        ListNode* fast = head;
        // stop when fast pointer reaches the end
        while (fast != nullptr && fast->next != nullptr) {
            // slow pointer moves one step, fast pointer moves two steps
            slow = slow->next;
            fast = fast->next->next;
        }
        // slow pointer points to the middle node
        return slow;
    }
};

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # initialize slow and fast pointers to head
        slow, fast = head, head
        # stop when the fast pointer reaches the end
        while fast is not None and fast.next is not None:
            # slow pointer moves one step, fast pointer moves two steps
            slow = slow.next
            fast = fast.next.next
        # slow pointer points to the middle node
        return slow

func middleNode(head *ListNode) *ListNode {
    // initialize slow and fast pointers to head
    slow, fast := head, head
    // stop when fast pointer reaches the end
    for fast != nil && fast.Next != nil {
        // slow pointer moves one step, fast pointer moves two steps
        slow = slow.Next
        fast = fast.Next.Next
    }
    // slow pointer points to the middle node
    return slow
}

var middleNode = function(head) {
    // initialize slow and fast pointers to head
    let slow = head, fast = head;
    // stop when fast pointer reaches the end
    while (fast !== null && fast.next !== null) {
        // slow pointer moves one step, fast pointer moves two steps
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow pointer points to the middle
    return slow;
};

It's important to note that if the length of the linked list is even, meaning there are two middle nodes, this method returns the latter one.

Additionally, with minor modifications, this code can be directly used for problems involving detecting cycles in a linked list.

Detecting Cycles in a Linked List

Determining whether a linked list contains a cycle is a classic problem, and the solution also uses the fast and slow pointer approach:

Every time the slow pointer slow moves one step forward, the fast pointer fast moves two steps forward.

If fast eventually reaches the end of the linked list normally, it means there is no cycle in the list. If fast meets slow while traversing, it indicates that fast is looping within the list, meaning there is a cycle.

You just need to slightly modify the code for finding the middle of the linked list:

class Solution {
    public boolean hasCycle(ListNode head) {
        // initialize slow and fast pointers to head
        ListNode slow = head, fast = head;
        // stop when the fast pointer reaches the end
        while (fast != null && fast.next != null) {
            // slow pointer moves one step, fast pointer moves two steps
            slow = slow.next;
            fast = fast.next.next;
            // if slow and fast pointers meet, it indicates a cycle
            if (slow == fast) {
                return true;
            }
        }
        // no cycle is present
        return false;
    }
}

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // initialize slow and fast pointers to head
        ListNode *slow = head, *fast = head;
        // stop when the fast pointer reaches the end
        while (fast != nullptr && fast->next != nullptr) {
            // slow pointer moves one step, fast pointer moves two steps
            slow = slow->next;
            fast = fast->next->next;
            // if slow and fast pointers meet, there is a cycle
            if (slow == fast) {
                return true;
            }
        }
        // no cycle
        return false;
    }
};

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # initialize slow and fast pointers to head
        slow, fast = head, head
        # stop when the fast pointer reaches the end
        while fast is not None and fast.next is not None:
            # slow pointer moves one step, fast pointer moves two steps
            slow = slow.next
            fast = fast.next.next
            # if slow and fast pointers meet, there is a cycle
            if slow == fast:
                return True
        # no cycle
        return False

func hasCycle(head *ListNode) bool {
    // initialize slow and fast pointers to head
    slow, fast := head, head
    // stop when the fast pointer reaches the end
    for fast != nil && fast.Next != nil {
        // slow pointer moves one step, fast pointer moves two steps
        slow = slow.Next
        fast = fast.Next.Next
        // if slow and fast pointers meet, a cycle is detected
        if slow == fast {
            return true
        }
    }
    // no cycle detected
    return false
}

var hasCycle = function(head) {
    // initialize slow and fast pointers to head
    let slow = head, fast = head;
    // stop when the fast pointer reaches the end
    while (fast !== null && fast.next !== null) {
        // move the slow pointer one step and the fast pointer two steps
        slow = slow.next;
        fast = fast.next.next;
        // if slow and fast pointers meet, it indicates a cycle
        if (slow === fast) {
            return true;
        }
    }
    // no cycle detected
    return false;
};

Certainly, there is an advanced version of this problem, which is LeetCode Problem 142 "Linked List Cycle II": How do you find the starting point of a cycle in a linked list?

To avoid confusion, let's consider an example. The starting point of the cycle is node 2 in the following diagram:

Let's first take a look at the code for finding the starting point of the cycle:

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;

        }
        // the above code is similar to the hasCycle function
        if (fast == null || fast.next == null) {
            // fast encountering a null pointer means there is no cycle
            return null;
        }

        // reassign to the head node
        slow = head;

        // move fast and slow pointers at the same
        // pace, the intersection point is the cycle's
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;

        }
        // The above code is similar to the hasCycle function
        if (fast == nullptr || fast->next == nullptr) {
            // fast encountering a null pointer means there is no cycle
            return nullptr;
        }

        // re-point to the head node
        slow = head;

        // move fast and slow pointers forward at the same
        // pace, the meeting point is the cycle's starting
        while (slow != fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break

        if not fast or not fast.next:
            return None
        slow = head 

        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

func detectCycle(head *ListNode) *ListNode {
    var fast, slow *ListNode
    fast, slow = head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break

        }
    }
    
    if fast == nil || fast.Next == nil {
        return nil
    }

    slow = head

    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

var detectCycle = function(head) {
    var fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;

    }
    // The above code is similar to the hasCycle function
    if (fast == null || fast.next == null) {
        // fast encountering a null pointer means there is no cycle
        return null;
    }

    // Re-point to the head node
    slow = head;

    // Fast and slow pointers move forward synchronously,
    // and the intersection point is the start of the
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
};

It can be observed that when the fast and slow pointers meet, if you set one of the pointers to the head node and let them move forward at the same speed, the node where they meet again is the starting point of the cycle.

Why does this work? Let's briefly explain the principle behind it.

Assume that when the fast and slow pointers meet, the slow pointer slow has taken k steps, then the fast pointer fast must have taken 2k steps:

The fast pointer must have taken k more steps than slow. These extra k steps are essentially the fast pointer circling within the loop, so the value of k is a "multiple of the loop's length."

Assume the distance from the meeting point to the start of the loop is m. Then, according to the diagram with the slow pointer, the distance from the loop's start to the head node head is k - m. This means if we move forward k - m steps from head, we will reach the loop's start.

Interestingly, if we move forward k - m steps from the meeting point, we also reach the loop's start. Based on the diagram with the fast pointer, starting from the meeting point and moving k steps brings us back to the meeting point, so moving k - m steps will definitely bring us to the loop's start:

Therefore, if we redirect one of the fast or slow pointers to head, and let both pointers move at the same speed, they will meet at the loop's start after k - m steps.

Do Two Linked Lists Intersect?

This is an interesting problem, also known as LeetCode Problem 160 "Intersection of Two Linked Lists," with the function signature as follows:

ListNode getIntersectionNode(ListNode headA, ListNode headB);

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB);

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:

func getIntersectionNode(headA *ListNode, headB *ListNode) *ListNode

var getIntersectionNode = function(headA, headB)

You are given the head nodes headA and headB of two linked lists, which may intersect.

If they intersect, your algorithm should return the intersecting node; if not, it should return null.

For instance, in the example provided, if the input linked lists are as shown in the image below:

Then your algorithm should return the node c1.

A straightforward approach might be to use a HashSet to record all the nodes of one linked list and then compare with the other linked list, but this requires extra space.

How could you solve this using only two pointers, without additional space?

The challenge lies in the fact that the lengths of the two linked lists may differ, so their nodes do not align:

If you move two pointers, p1 and p2, along the two linked lists, they cannot simultaneously reach the common node, and thus, cannot find the intersecting node c1.

The key to solving this problem is to make p1 and p2 reach the intersecting node c1 simultaneously through some method.

So, we can let p1 traverse through list A and then start traversing list B, while p2 traverses through list B and then starts traversing list A. This approach effectively "logically" connects the two linked lists.

By doing this, p1 and p2 can enter the common section simultaneously, reaching the intersecting node c1:

You might wonder, if the two linked lists do not intersect, will it correctly return null?

This logic can indeed handle such a situation, as it treats the c1 node as a null pointer, correctly returning null.

Following this idea, the code can be written as follows:

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // p1 points to the head node of list A, p2 points to the head node of list B
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            // p1 takes a step, if it reaches the end of list A, switch to list B
            if (p1 == null) {
                p1 = headB;
            } else {
                p1 = p1.next;
            }
            // p2 takes a step, if it reaches the end of list B, switch to list A
            if (p2 == null) {
                p2 = headA;
            } else{
                p2 = p2.next;
            }
        }
        return p1;
    }
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // p1 points to the head of list A, p2 points to the head of list B
        ListNode *p1 = headA, *p2 = headB;
        while (p1 != p2) {
            // p1 moves one step, if it reaches the end of list A, switch to list B
            if (p1 == nullptr) {
                p1 = headB;
            } else {
                p1 = p1->next;
            }
            // p2 moves one step, if it reaches the end of list B, switch to list A
            if (p2 == nullptr) {
                p2 = headA;
            } else {
                p2 = p2->next;
            }
        }
        return p1;
    }
};

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # p1 points to the head node of list A, p2 points to the head node of list B
        p1, p2 = headA, headB
        while p1 != p2:
            # p1 moves one step, if it reaches the end of list A, switch to list B
            p1 = p1.next if p1 else headB
            # p2 moves one step, if it reaches the end of list B, switch to list A
            p2 = p2.next if p2 else headA
        return p1

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // p1 points to the head node of list A, p2 points to the head node of list B
    p1 := headA
    p2 := headB
    for p1 != p2 {
        // p1 takes a step, if it reaches the end of list A, switch to list B
        if p1 == nil {
            p1 = headB
        } else {
            p1 = p1.Next
        }
        // p2 takes a step, if it reaches the end of list B, switch to list A
        if p2 == nil {
            p2 = headA
        } else {
            p2 = p2.Next
        }
    }
    return p1
}

var getIntersectionNode = function(headA, headB) {
    // p1 points to the head node of list A, p2 points to the head node of list B
    let p1 = headA, p2 = headB;
    while (p1 !== p2) {
        // p1 takes one step, if it reaches the end of list A, switch to list B
        if (p1 === null) {
            p1 = headB;
        } else {
            p1 = p1.next;
        }
        // p2 takes one step, if it reaches the end of list B, switch to list A
        if (p2 === null) {
            p2 = headA;
        } else {
            p2 = p2.next;
        }
    }
    return p1;
};

Thus, this problem is solved with a space complexity of $O(1)$ and a time complexity of $O(N)$.

These are all the techniques for singly linked lists. I hope they inspire you.

Update on 2022/1/24:

Several excellent readers have proposed alternative approaches to the last problem, "Finding the Intersection of Two Linked Lists," which are also included here.

Initially, a reader mentioned that if you connect the two linked lists end to end, the problem of "finding the intersection of two linked lists" transforms into the previously discussed problem of "finding the start of a loop":

Honestly, I did not think of this approach. It's a clever transformation! However, it's important to note that the problem states you should not alter the original structure of the linked lists, so after transforming the input linked lists into a circular linked list to solve the problem, remember to revert them back; otherwise, you won't pass.

Additionally, another reader suggested that since the core of "finding the intersection of two linked lists" lies in having pointers p1 and p2 simultaneously reach the intersecting node c1, you can achieve this by pre-calculating the lengths of the two linked lists. The specific code is as follows:

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // calculate the lengths of the two linked lists
        for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
            lenA++;
        }
        for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
            lenB++;
        }
        // make p1 and p2 the same distance from the end
        ListNode p1 = headA, p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        // check if the two pointers become the same, when p1 == p2, there are two scenarios:
        // 1. either the two linked lists do not
        // intersect, they both move to the end null
        // 2. or the two linked lists intersect, they
        // reach the intersection point of the two
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0, lenB = 0;
        // calculate the lengths of the two linked lists
        for (ListNode* p1 = headA; p1 != nullptr; p1 = p1->next) {
            lenA++;
        }
        for (ListNode* p2 = headB; p2 != nullptr; p2 = p2->next) {
            lenB++;
        }
        // make the distance to the end equal for p1 and p2
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1->next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2->next;
            }
        }
        // check if the two pointers are the same, there are two cases when p1 == p2:
        // 1. either the two linked lists do not
        // intersect, and they both reach the end
        // 2. or the two linked lists intersect, and they
        // reach the intersection point of the two linked
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA, lenB = 0, 0
        # calculate the length of both linked lists
        p1, p2 = headA, headB
        while p1:
            lenA += 1
            p1 = p1.next
        while p2:
            lenB += 1
            p2 = p2.next
        
        # make p1 and p2 reach the same distance from the end
        p1, p2 = headA, headB
        if lenA > lenB:
            for _ in range(lenA - lenB):
                p1 = p1.next
        else:
            for _ in range(lenB - lenA):
                p2 = p2.next
        
        # check if the two pointers are the same, there are two cases when p1 == p2:
        # 1. either the two linked lists do not intersect and both reach the end null pointer
        # 2. or the two linked lists intersect and they reach the intersection point
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        
        return p1

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    lenA, lenB := 0, 0
    // calculate the lengths of the two linked lists
    for p1 := headA; p1 != nil; p1 = p1.Next {
        lenA++
    }
    for p2 := headB; p2 != nil; p2 = p2.Next {
        lenB++
    }
    // make p1 and p2 reach the same distance from the end
    p1, p2 := headA, headB
    if lenA > lenB {
        for i := 0; i < lenA - lenB; i++ {
            p1 = p1.Next
        }
    } else {
        for i := 0; i < lenB - lenA; i++ {
            p2 = p2.Next
        }
    }
    // see if the two pointers will be the same, when p1 == p2 there are two cases:
    // 1. either the two linked lists do not intersect, and
    // they simultaneously reach the null pointer at the end
    // 2. or the two linked lists intersect, and they
    // reach the intersection point of the two linked
    for p1 != p2 {
        p1 = p1.Next
        p2 = p2.Next
    }
    return p1
}

var getIntersectionNode = function(headA, headB) {
    let lenA = 0, lenB = 0;
    
    // calculate the lengths of the two linked lists
    for (let p1 = headA; p1 != null; p1 = p1.next) {
        lenA++;
    }
    for (let p2 = headB; p2 != null; p2 = p2.next) {
        lenB++;
    }
    
    // make p1 and p2 have the same distance to the end
    let p1 = headA, p2 = headB;
    if (lenA > lenB) {
        for (let i = 0; i < lenA - lenB; i++) {
            p1 = p1.next;
        }
    } else {
        for (let i = 0; i < lenB - lenA; i++) {
            p2 = p2.next;
        }
    }
    
    // check if the two pointers become the same, there are two cases when p1 == p2:
    // 1. either the two linked lists do not
    // intersect, and they both reach the null pointer
    // 2. or the two linked lists intersect, and they reach the intersection point
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return p1;
};

Although the code might be a bit longer, the time complexity remains $O(N)$, and it is somewhat easier to understand.

In conclusion, my solution is not necessarily the most optimal or correct one. I encourage everyone to raise their own questions and thoughts in the comments section. I am also pleased to discuss more problem-solving approaches with you all.

This concludes the discussion on the two-pointer techniques related to linked lists. For more extended applications of these techniques, see More Classic Linked List Two-Pointer Problems.