April 25, 2022
Here is the link.
C# | Optimal solution O(N) time complexity O(1) space
April 25, 2022
Introduction
It is important to learn optimal solution from Leetcode premium solution. I came cross the optimal solution and idea from here.
Optimal solution ideas | StefanPochmann
Solution 1: Reversed first half == Second half?
Phase 1: Reverse the first half while finding the middle.
Phase 2: Compare the reversed first half with the second half.
Leetcode premium discuss
Approach 3: Reverse Second Half In-place
Intuition
The only way we can avoid using O(n)O(n) extra space is by modifying the input in-place.
The strategy we can use is to reverse the second half of the Linked List in-place (modifying the Linked List structure), and then comparing it with the first half. Afterwards, we should re-reverse the second half and put the list back together. While you don't need to restore the list to pass the test cases, it is still good programming practice because the function could be a part of a bigger program that doesn't want the Linked List broken.
Algorithm
Specifically, the steps we need to do are:
- Find the end of the first half.
- Reverse the second half.
- Determine whether or not there is a palindrome.
- Restore the list.
- Return the result.
To do step 1, we could count the number of nodes, calculate how many nodes are in the first half, and then iterate back down the list to find the end of the first half. Or, we could do it in a single parse using the two runners pointer technique. Either is acceptable, however we'll have a look at the two runners pointer technique here.
Imagine we have 2 runners one fast and one slow, running down the nodes of the Linked List. In each second, the fast runner moves down 2 nodes, and the slow runner just 1 node. By the time the fast runner gets to the end of the list, the slow runner will be half way. By representing the runners as pointers, and moving them down the list at the corresponding speeds, we can use this trick to find the middle of the list, and then split the list into two halves.
If there is an odd-number of nodes, then the "middle" node should remain attached to the first half.
Step 2 uses the algorithm that can be found in the solution article for the Reverse Linked List problem to reverse the second half of the list.
Step 3 is fairly straightforward. Remember that we have the first half, which might also contain a "middle" node at the end, and the second half, which is reversed. We can step down the lists simultaneously ensuring the node values are equal. When the node we're up to in the second list is null, we know we're done. If there was a middle value attached to the end of the first list, it is correctly ignored by the algorithm. The result should be saved, but not returned, as we still need to restore the list.
Step 4 requires using the same function you used for step 2, and then for step 5 the saved result should be returned.
Things to argue | end of first half | Why it is better to choose end of first half?
It is interesting to learn that function design is to find end of first half node instead of the first node in second half. I will think about more later.
The following C# code passes online judge.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _234_palindrom_linked_list
{
class Program
{
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val=0, ListNode next=null) {
this.val = val;
this.next = next;
}
}
static void Main(string[] args)
{
}
public bool IsPalindrome(ListNode head)
{
if (head == null)
{
return true;
}
var firstHalfEnd = endOfFirstHalf(head);
var secondHalfStart = reverseList(firstHalfEnd.next);
ListNode p1 = head;
ListNode p2 = secondHalfStart;
bool result = true;
while (result && p2 != null)
{
if (p1.val != p2.val) result = false;
p1 = p1.next;
p2 = p2.next;
}
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head)
{
ListNode prev = null;
ListNode curr = head;
while (curr != null)
{
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head)
{
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null)
{
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
}
