Two Pointer Techniques for Linked List Problems

labuladongOriginalAbout 8592 words

Note

Now all the plugins has supported English. I'm still improving the website...

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 should first learn:

This article summarizes basic techniques for singly linked lists, with each technique 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 in a singly linked list
Finding the midpoint of a singly linked list
Detecting a cycle in a singly linked list and finding the starting node of the cycle
Determining if two singly linked lists intersect and finding the intersection point

These solutions all utilize the two-pointer technique, which is extensively used in problems related to singly linked lists. Let's explore each technique one by one.

Merging Two Sorted Linked Lists

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

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:

To visually understand, the logic of this algorithm is similar to zipping up a zipper, where l1 and l2 resemble the teeth on either side of the zipper, and the pointer p acts like the zipper slider, merging the two sorted lists.

The code also uses a common technique in linked list problems called the "dummy head node". You can try it yourself—if you don't use the dummy node, the code becomes a bit more complicated as you need to handle the case where pointer p is null. With the dummy node serving as a placeholder, you can avoid dealing with null pointers, reducing the complexity of the code.

When to Use a Dummy Head Node

Readers often ask me when to use a dummy head node. Here's a summary: When you need to create a new linked list, using a dummy head node can simplify edge case handling.

For example, when merging two sorted lists into a new sorted list, aren't you creating a new list? Or if you want to split a list into two lists, aren't you also creating new lists? In these scenarios, using a dummy head node can simplify edge case handling.

Decomposing a Singly Linked List

Let's 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

While merging two sorted lists involves combining them, here you need to decompose a list into two. Specifically, you can split the original list into two smaller lists: one with elements less than x, and the other with elements 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 lists. Let's look at the code details, paying attention to the use of the dummy head node:

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 without creating new nodes, it might be necessary to disconnect the nodes from the original linked list. It's a good practice to disconnect nodes in such cases to avoid errors.

Merging k Sorted 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 each poll or add operation is $O(logk)$ . All the nodes from the linked lists will be added to and removed from pq, thus 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 linked lists.

The k-th Node from the End of a Singly Linked List

Finding the k-th node from the beginning of a singly linked list is straightforward; a simple for loop can do it. 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 node from the end is the (n - k + 1)-th node from the beginning, which is also a matter of a for loop, right?

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

In other words, this approach requires two traversals of the linked list to find the k-th node from the end.

So, can we find the k-th node from the end with just one traversal? It is possible, and if this problem arises in an interview, the interviewer would likely expect you to provide a solution that only requires one traversal.

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

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

At this point, p1 needs to move n - k more steps to reach the end of the list:

Meanwhile, introduce another pointer p2 pointing to the head of the list:

Next, move both p1 and p2 forward simultaneously. When p1 reaches the null pointer at the end of the list after moving n - k steps, p2 will have moved n - k steps from head, stopping at the (n - k + 1)-th node, which is exactly the k-th node from the end:

In this way, by traversing the list only once, you obtain the k-th node from the end, 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, if we use big O notation to calculate time complexity, both traversing the list once and twice have a time complexity of $O(N)$ . However, the algorithm mentioned above 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 here is quite simple. To remove the n-th node from the end, you need a reference to the (n + 1)-th node from the end. We can use the findFromEnd function we implemented to achieve this.

However, note that we employ the technique of using a dummy head node to prevent null pointer issues. For example, if there are 5 nodes in the linked list and the task is to delete the 5th node from the end, which is the first node, the algorithm would require finding the 6th node from the end first. Since there is no node before the first node, this would cause an error.

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

Middle of a Singly Linked List

LeetCode Problem 876, "Middle of the Linked List," is a related problem. The challenge is that we cannot directly obtain the length n of a singly linked list. A conventional method is to traverse the list to calculate n, then traverse again to find 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 ingenuity with the "fast and slow pointers" technique:

We have two pointers, slow and fast, initially pointing to the head of the list.

Every time the slow pointer slow moves one step forward, the fast pointer fast moves two steps forward. Thus, when fast reaches the end of the list, slow will point to the middle node.

The code implementation for the above logic 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 a linked list contains a cycle, how do you find the starting point of this cycle?

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

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

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, you can set either pointer to the head node and let them move forward at the same speed. The node where they meet again is the start of the cycle.

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

Let's assume that when the fast and slow pointers meet, the slow pointer slow has taken k steps. Thus, the fast pointer fast must have taken 2k steps:

The fast pointer has taken k more steps than the slow pointer, which means these extra k steps are the laps the fast pointer has completed within the cycle. Therefore, k is a multiple of the cycle's length.

Assuming the distance from the meeting point to the start of the cycle is m, the distance from the head node head to the start of the cycle would be k - m. This means moving forward k - m steps from head will reach the start of the cycle.

Interestingly, if you move k - m steps from the meeting point, you will also reach the start of the cycle. Referring to the fast pointer in the diagram, taking k steps from the meeting point returns to the meeting point itself, so k - m steps will definitely reach the start of the cycle:

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

Do Two Linked Lists Intersect?

This is an interesting problem, which is also LeetCode problem 160 "Intersection of Two Linked Lists" with the following function signature:

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

Decomposing a Singly Linked List

Merging k Sorted Lists

The k-th Node from the End of a Singly Linked List

Middle of a Singly Linked List

Detecting Cycles in a Linked List

Do Two Linked Lists Intersect?