This problem can be divided into two algorithmic problems: [Middle of the Linked List] and [Reverse Linked List].
Middle of the Linked List (Two Pointers)#
With the help of two pointers, fast and slow, the fast pointer moves 2 steps each round, and the slow pointer moves 1 step each round.
The number of steps taken by fast is always twice that of slow, so when the fast pointer traverses the entire linked list, the slow pointer points to the middle node of the linked list. Since a linked list with an even length has two middle nodes, two cases need to be considered:
- Odd length of the linked list: When
fastreaches the [tail node] of the linked list,slowis exactly at the [middle node]. - Even length of the linked list: When
fastreaches [null] (beyond the [tail node]),slowis exactly at the [second middle node].
Based on the above rules, we should exit the loop when fast encounters or goes beyond the tail node, and return slow.
// Linked list with odd length
ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null))))));
// Linked list with even length
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));
Console.WriteLine("odd head middleNode val: {0}", MiddleNode(oddHead).Val);
Console.WriteLine("even head middleNode val: {0}", MiddleNode(evenHead).Val);
// Middle of the Linked List
ListNode MiddleNode(ListNode head)
{
// Initialize the fast and slow pointers, both pointing to the head node of the linked list
ListNode? fast = head, slow = head;
// Exit the loop when fast encounters or goes beyond the tail node
while (fast != null && fast.Next != null)
{
fast = fast.Next.Next;
slow = slow!.Next;
}
return slow!;
}
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}
If the question requires returning the "first middle node", then we should exit the loop when fast encounters the tail node or its predecessor. In this case, modify the condition to while fast.next and fast.next.next.
Reverse Linked List#
Approach 1: Iteration (Two Pointers)#
Traverse the linked list and modify the next reference pointer when accessing each node, as shown in the code comments.
// Initialize the linked list
ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null))))));
ListNode reverseNode = ReverseNode(node);
while (reverseNode != null)
{
Console.WriteLine("reverseNode val: {0}", reverseNode.Val);
reverseNode = reverseNode.Next;
}
// Reverse Linked List: Iteration (Two Pointers)
ListNode ReverseNode(ListNode head)
{
// Initialize pre and cur, pointing to null and the head node respectively
ListNode pre = null, cur = head;
while (cur != null)
{
ListNode tmp = cur.Next; // Temporarily store the successor node
cur.Next = pre; // Modify the reference pointer
pre = cur; // Temporarily store the current node
cur = tmp; // Visit the next node
}
return pre;
}
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}
Final Code#
// Q: Reverse the first half of the linked list and connect it with the second half
// Initialize a linked list with odd length
using System.Diagnostics;
ListNode oddHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null))))));
// Initialize a linked list with even length
ListNode evenHead = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6, null))))));
// Reverse the first half of the linked list and connect it with the second half
Console.WriteLine("Linked list with odd length:");
Stopwatch sw = Stopwatch.StartNew();
ListNode? finalOddHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(oddHead);
sw.Stop();
Console.WriteLine($"Time elapsed: {sw.ElapsedMilliseconds}ms");
while (finalOddHead != null)
{
Console.WriteLine(finalOddHead.Val);
finalOddHead = finalOddHead.Next;
}
// Reverse the first half of the linked list and connect it with the second half
Console.WriteLine("Linked list with even length:");
sw = Stopwatch.StartNew();
ListNode? finalEvenHead = ReverseLeftOfMiddleAndCombineRightOfMiddle(evenHead);
sw.Stop();
Console.WriteLine($"Time elapsed: {sw.ElapsedMilliseconds}ms");
while (finalEvenHead != null)
{
Console.WriteLine(finalEvenHead.Val);
finalEvenHead = finalEvenHead.Next;
}
ListNode ReverseLeftOfMiddleAndCombineRightOfMiddle(ListNode head)
{
// Find the middle node of the linked list
// Use two pointers, fast and slow, where the fast pointer moves 2 steps each time and the slow pointer moves 1 step each time. Exit the loop when the fast pointer encounters or goes beyond the tail node, and return the slow pointer, which represents the middle node.
ListNode fast = head, slow = head;
while (fast != null && fast.Next != null)
{
fast = fast.Next.Next;
slow = slow.Next;
}
// When the length of the linked list is odd, slow is exactly the middle node
// When the length of the linked list is even, slow is the last node of the two middle nodes
ListNode middleNode = slow;
// Reverse the left part of the linked list
// Use iteration (two pointers)
// Here, we make pre point to the middle node, so that after reversing the left part of the linked list, the last node of the left part points to the right part of the linked list (the middle node), thus connecting the reversed linked list with the right part
ListNode pre = middleNode, cur = head;
// The current node in the current loop is not null and is before the middle node, so only reverse the left part of the linked list
while (cur != null && cur.Val != middleNode.Val)
{
// Temporarily store the successor node
ListNode tmp = cur.Next;
// Modify the reference pointer
cur.Next = pre;
// Temporarily store the current node
pre = cur;
// Visit the next node
cur = tmp;
}
return pre;
}
// Singly linked list structure
class ListNode
{
public int Val { get; set; }
public ListNode? Next { get; set; }
public ListNode(int val, ListNode? next)
{
Val = val;
Next = next;
}
}