Two Pointer Techniques for Linked List Problems

labuladongOriginalAbout 8664 words

This article will resolve

LeetCode	Difficulty
141. Linked List Cycle	🟢
142. Linked List Cycle II	🟠
160. Intersection of Two Linked Lists	🟢
19. Remove Nth Node From End of List	🟠
21. Merge Two Sorted Lists	🟢
23. Merge k Sorted Lists	🔴
86. Partition List	🟠
876. Middle of the Linked List	🟢

Prerequisite Knowledge

Before reading this article, you need to learn:

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

Merging Two Sorted Linked Lists
Decomposing a Linked List
Merging k Sorted Linked Lists
Finding the k-th Last Node of a Singly Linked List
Finding the Midpoint of a Singly Linked List
Detecting a Cycle in a Singly Linked List and Finding the Cycle's Start
Checking if Two Singly Linked Lists Intersect and Finding the Intersection Point

These solutions all use the two-pointer technique, which is widely applicable to singly linked list problems. Let's take a closer look at each one.

Merging Two Sorted Linked Lists

This is the most basic linked list technique. LeetCode Problem 21, "Merge Two Sorted Lists," addresses this problem. 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.

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

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

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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

Our while loop compares the size of p1 and p2 each time, attaching the smaller node to the result list. See the GIF below:

Conceptually, this algorithm works like a zipper, where l1, l2 are like the teeth on either side of the zipper, and the pointer p acts like the zipper slider, merging two sorted linked lists.

The code also uses a very common technique in linked list problems called a "dummy node." You can try it; if you don't use the dummy node, the code becomes more complicated and requires extra handling for when the pointer p is null. With the dummy node as a placeholder, it avoids dealing with null pointers, reducing code complexity.

When to Use a Dummy Node

Readers often ask me when to use a dummy node. Here is a summary: When you need to create a new linked list, you can use a dummy node to simplify handling edge cases.

For instance, when merging two sorted linked lists into a new sorted linked list, are you not creating a new linked list? Similarly, if you want to split a linked list into two, are you not also creating new linked lists? In these cases, using a dummy node can simplify handling edge cases.

Decomposition of 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 requires combining, here you need to decompose, splitting the original list into two. Specifically, we can divide the original list into two smaller lists: one where all elements are less than x, and another where all elements are greater than or equal to x. Finally, connect these two lists together to achieve the desired result.

The overall logic is very similar to merging sorted linked lists. You can see the details directly in the code, paying attention to the use of dummy nodes:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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;

In general, if we need to attach nodes from the original linked list to a new linked list, instead of creating new nodes for the new linked list, it might be necessary to disconnect the nodes from the original linked list. It is a good habit to disconnect the original linked list nodes in such situations to avoid errors.

Merging `k` Sorted Linked Lists

Consider LeetCode Problem 23 "Merge k Sorted Lists":

23. Merge k Sorted Lists | LeetCode | 🔴

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

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

Example 2:

Input: lists = []
Output: []

Example 3:

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

Constraints:

k == lists.length
0 <= k <= 10⁴
0 <= lists[i].length <= 500
-10⁴ <= lists[i][j] <= 10⁴
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10⁴.

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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 for a single poll or add operation is $O(logk)$ . All the nodes of the linked lists will be added to and removed from pq, so the overall time complexity of the algorithm is $O(Nlogk)$ , where $k$ is the number of linked lists and $N$ is the total number of nodes in these lists.

Note

There is another classic solution to this problem, which is explained in detail in Divide and Conquer Algorithm Core Framework. It is not expanded upon here.

The `k`-th Last Node of a Singly Linked List

Finding the k-th node from the start of a singly linked list is straightforward; you can find it with a single for loop. But how do you find the k-th node from the end?

You might say, assuming the list has n nodes, the k-th node from the end is the n - k + 1-th node from the start, which is also a matter of a for loop, right?

Yes, but typically, an algorithm problem only provides you with a ListNode head node representing a singly linked list, so you cannot directly determine the length n of this list. You need to first traverse the list to calculate n, and then traverse the list again to find the n - k + 1-th node.

In other words, this solution requires traversing the list twice to find the k-th last node.

Can we find the k-th last node by traversing the list only once? Yes, it is possible, and if this question comes up in an interview, the interviewer would likely be looking for a solution that requires only one traversal.

This solution is quite clever. Suppose k = 2, the idea is as follows:

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

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

At this moment, use another pointer p2 to point to the head node head:

Next, it's quite clear. Let p1 and p2 move forward simultaneously; when p1 reaches the end of the list after moving n - k steps, p2 will have moved n - k steps from the 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 obtain the k-th last node p2.

The code for the above logic is as follows:

java 🟢

// 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;
}

cpp 🤖

// 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;
}

python 🤖

# 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

go 🤖

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

javascript 🤖

// 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, using big O notation to calculate time complexity, whether traversing the list once or twice, both have a time complexity of $O(N)$ . However, this algorithm is more skillful.

Many linked list-related algorithm problems use this technique, 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 n^th 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:

java 🟢

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

cpp 🤖

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

python 🤖

# 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

go 🤖

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
}

javascript 🤖

// 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
};

The logic is straightforward. To remove the nth node from the end, you must get a reference to the n + 1th node from the end, which can be done using our implemented findFromEnd.

However, note that we used the technique of a dummy head node to prevent null pointer scenarios. For example, if the list has a total of 5 nodes and you are asked to remove the 5th node from the end, which is the first node, the algorithm should locate the 6th node from the end. But there is no node before the first node, which would cause an error.

With the presence of our dummy node dummy, this issue is avoided, allowing for correct removal in such cases.

Midpoint of a Singly Linked List

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

If you want to find the middle node in a single traversal, you need to be a bit clever and use the "slow and fast pointers" technique:

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

Each time the slow pointer slow advances one step, the fast pointer fast advances two steps. Thus, when fast reaches the end of the list, slow points to the middle of the list.

The code implementation of the above idea is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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 linked list has an even number of nodes, meaning there are two middle nodes, our solution returns the latter node.

Additionally, with minor modifications, this code can be directly applied to the problem of 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 fast and slow pointers:

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

If fast can reach the end of the list normally, it indicates there is no cycle in the list. However, if fast eventually meets slow, it means fast is moving in circles within the list, indicating the list contains a cycle.

Only minor modifications are needed for the code used to find the middle of the linked list:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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

Of course, there is an advanced version of this problem, which is LeetCode problem 142 "Linked List Cycle II": If there is a cycle in the linked list, how do you calculate the starting point of this cycle?

For example, the starting point of the cycle is node 2 in the following diagram:

Let's directly look at the solution code for finding the cycle's starting point:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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

When the fast and slow pointers meet, redirect either pointer to the head of the list, then let them move at the same speed. The node where they meet again will be the start of the cycle.

Why is this method used? Here's a brief explanation of the principle.

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:

fast has taken k more steps than slow, and these extra k steps are essentially fast circling around the cycle, meaning k is a multiple of the cycle's length.

Assume the distance from the meeting point to the start of the cycle is m. From the diagram's slow pointer, the distance from the start of the cycle to the head node head is k - m, meaning if you move k - m steps from head, you reach the start of the cycle.

Interestingly, if you continue moving k - m steps from the meeting point, you will also reach the start of the cycle. From the diagram's fast pointer, moving k steps from the meeting point circles back to the meeting point, so moving k - m steps must reach the start of the cycle:

Therefore, by redirecting either the fast or slow pointer to head and moving both pointers at the same speed, they will meet after k - m steps, and the meeting point will be the start of the cycle.

Do Two Linked Lists Intersect

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

java 🟢

ListNode getIntersectionNode(ListNode headA, ListNode headB);

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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

This way, the 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, and I hope they inspire you.

Updated on 2022/1/24:

Several insightful readers have proposed alternative approaches to the final problem "Finding the Intersection of Two Linked Lists" in the comments section, which I will include here.

Firstly, a reader suggested that if you connect the ends of the two linked lists, the problem of "Finding the Intersection of Two Linked Lists" transforms into the earlier problem of "Finding the Start of a Cycle":

Honestly, I hadn't thought of this approach, and it is indeed a clever transformation! However, it is important to note that the problem specifies not to alter the structure of the original linked lists. Therefore, if you solve it by converting the input linked lists into a circular form, remember to revert them back, otherwise, it won't be acceptable.

Additionally, another reader pointed out that since the core of "Finding the Intersection of Two Linked Lists" is to ensure that pointers p1 and p2 reach the intersection node c1 simultaneously, you can achieve this by calculating the lengths of the two linked lists in advance. The specific code is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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
}

javascript 🤖

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.

Related Problems

You can install my Chrome extension then open the link.

LeetCode	Difficulty
109. Convert Sorted List to Binary Search Tree	🟠
1257. Smallest Common Region🔒	🟠
1650. Lowest Common Ancestor of a Binary Tree III🔒	🟠
1836. Remove Duplicates From an Unsorted Linked List🔒	🟠
2. Add Two Numbers	🟠
234. Palindrome Linked List	🟢
264. Ugly Number II	🟠
313. Super Ugly Number	🟠
355. Design Twitter	🟠
360. Sort Transformed Array🔒	🟠
373. Find K Pairs with Smallest Sums	🟠
378. Kth Smallest Element in a Sorted Matrix	🟠
431. Encode N-ary Tree to Binary Tree🔒	🔴
88. Merge Sorted Array	🟢
97. Interleaving String	🟠
977. Squares of a Sorted Array	🟢

Two Pointer Techniques for Linked List Problems

141. 环形链表 https://leetcode.cn/problems/linked-list-cycle

141. Linked List Cycle https://leetcode.com/problems/linked-list-cycle

142. 环形链表 II https://leetcode.cn/problems/linked-list-cycle-ii

142. Linked List Cycle II https://leetcode.com/problems/linked-list-cycle-ii

160. 相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists

160. Intersection of Two Linked Lists https://leetcode.com/problems/intersection-of-two-linked-lists

19. 删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list

19. Remove Nth Node From End of List https://leetcode.com/problems/remove-nth-node-from-end-of-list

21. 合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists

21. Merge Two Sorted Lists https://leetcode.com/problems/merge-two-sorted-lists

23. 合并K个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists

23. Merge k Sorted Lists https://leetcode.com/problems/merge-k-sorted-lists

86. 分隔链表 https://leetcode.cn/problems/partition-list

86. Partition List https://leetcode.com/problems/partition-list

876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list

876. Middle of the Linked List https://leetcode.com/problems/middle-of-the-linked-list

剑指 Offer 22. 链表中倒数第k个节点 https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

剑指 Offer 22. 链表中倒数第k个节点 LCOF https://leetcode.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

Merging Two Sorted Linked Lists

Decomposition of a Singly Linked List

Merging `k` Sorted Linked Lists

The `k`-th Last Node of a Singly Linked List

Midpoint of a Singly Linked List

Detecting Cycles in a Linked List

Do Two Linked Lists Intersect

Two Pointer Techniques for Linked List Problems

141. 环形链表 https://leetcode.cn/problems/linked-list-cycle

141. Linked List Cycle https://leetcode.com/problems/linked-list-cycle

142. 环形链表 II https://leetcode.cn/problems/linked-list-cycle-ii

142. Linked List Cycle II https://leetcode.com/problems/linked-list-cycle-ii

160. 相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists

160. Intersection of Two Linked Lists https://leetcode.com/problems/intersection-of-two-linked-lists

19. 删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list

19. Remove Nth Node From End of List https://leetcode.com/problems/remove-nth-node-from-end-of-list

21. 合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists

21. Merge Two Sorted Lists https://leetcode.com/problems/merge-two-sorted-lists

23. 合并K个升序链表 https://leetcode.cn/problems/merge-k-sorted-lists

23. Merge k Sorted Lists https://leetcode.com/problems/merge-k-sorted-lists

86. 分隔链表 https://leetcode.cn/problems/partition-list

86. Partition List https://leetcode.com/problems/partition-list

876. 链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list

876. Middle of the Linked List https://leetcode.com/problems/middle-of-the-linked-list

剑指 Offer 22. 链表中倒数第k个节点 https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

剑指 Offer 22. 链表中倒数第k个节点 LCOF https://leetcode.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

Merging Two Sorted Linked Lists

Decomposition of a Singly Linked List

Merging k Sorted Linked Lists

The k-th Last Node of a Singly Linked List

Midpoint of a Singly Linked List

Detecting Cycles in a Linked List

Do Two Linked Lists Intersect

Merging `k` Sorted Linked Lists

The `k`-th Last Node of a Singly Linked List