Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

 

public bool IsPalindrome(ListNode head) {if(head == null) return true;// Reverse the head;ListNode standForward  = new ListNode(0);ListNode stand  =standForward;ListNode newHead = null;while(head != null)    {        standForward.next = new ListNode(head.val);        ListNode nextNode = head.next;        head.next = newHead;        newHead = head;        head = nextNode;                standForward = standForward.next;    }while(newHead != null){    if(stand.next.val != newHead.val) return false;    stand=stand.next ;    newHead = newHead.next;}return true;}

 

 

if use space O(1), we need to use 2 pointer to find the middle pointer of linked list and then reverse the second part of the linked list.

public bool IsPalindrome(ListNode head) {         if(head == null) return true;         ListNode slow = head;         ListNode fast = head;         ListNode nextNode = null;         ListNode newHead = null;                  //get middle pointer of the linked list         while(fast != null && fast.next != null)         {             slow = slow.next;             fast = fast.next.next;         }                   while(slow != null)             {                 nextNode = slow.next;                 slow.next = newHead;                 newHead = slow;                 slow = nextNode;             }         while(head != null && newHead != null)         {             if(head.val != newHead.val) return false;             head = head.next;             newHead = newHead.next;         }         return true;     }