C# Reverse Clone the list then compare O(n) in time and O(n) in memory.


  • 0
    O
    // Make a reversed clone of the list
     public ListNode ReverseCloneList(ListNode head)
    {
      if (head == null)
      return null;
    
      var node = head;
      ListNode prev = null;
      ListNode newhead = null;
      while (node != null)
      {
        newhead = new ListNode(node.val);
        newhead.next = prev;
        prev = newhead;
        node = node.next;
      }
    
      return newhead;
    }
    
    public bool IsPalindrome(ListNode head) {
             if (head == null || head.next == null)
        return true;
    
      // Reverse and clone the list
      ListNode reversedhead = ReverseCloneList(head);
    
      // Then compare
      while (reversedhead != null && head != null && reversedhead.val == head.val)
      {
        reversedhead = reversedhead.next;
        head = head.next;
      }
    
      return (reversedhead == null && head == null); 
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.