C# accepted, reverse the second half of list, and compare wth the first half


  • 0
    R
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public bool IsPalindrome(ListNode head) 
        {
            // get length
            int length = 0;
            ListNode temp = head;
            while (temp != null)
            {
                length++;
                temp = temp.next;
            }
            
            if (length <= 1)
            {
                return true;
            }
            
            // finding the beginning node of the other half of list
            int newListPos = length % 2 == 0 ? (length / 2) : (length / 2 + 1);
            temp = head;
            int pos = 0;
            while (pos < newListPos)
            {
                pos++;
                temp = temp.next;
            }
    
            // compare two halves of list
            bool result = true;
            ListNode l1 = head;
            ListNode l2 = ReverseLinkedList(temp);
            while (l1 != null && l2 != null)
            {
                if (l1.val != l2.val)
                {
                    result = false;
                    break;
                }
                l1 = l1.next;
                l2 = l2.next;
            }
            return result;
        }
        
            public static ListNode ReverseLinkedList(ListNode head)
            {
                ListNode newHead = new ListNode(0);
                ListNode current = head;
                while (current != null)
                {
                    ListNode next = current.next;
                    current.next = newHead;
                    newHead = current;
                    current = next;
                }
                head.next = null;
                return newHead;
            }

Log in to reply
 

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