C# solution: slow & fast pointers, reverse


  • 0
    B
    public class Solution 
    {
        public bool IsPalindrome(ListNode head) 
    	{
    		if (head == null) return true;
    		if (head.next == null) return true;
    
    		ListNode pre = null;
            var slow = head;
    		var fast = head;
    
    		while(fast != null && fast.next != null)
    		{
    			pre = slow;
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    
    		pre.next = null;
    		var newHead = Reverse(slow);
    
    		var cur1 = head;
    		var cur2 = newHead;
    		while(cur1 != null)
    		{
    			if (cur1.val != cur2.val)
    			{
    				return false;
    			}
    			
    			cur1 = cur1.next;
    			cur2 = cur2.next;
    		}
    
    		return true;
        }
    
    	private ListNode Reverse(ListNode head)
    	{
    		var dummy = new ListNode(-1);
    		dummy.next = head;
    
    		while(head.next != null)
    		{
    			var next = head.next;
    			head.next = head.next.next;
    			next.next = dummy.next;
    			dummy.next = next;
    		}
    
    		var newHead = dummy.next;
    		dummy.next = null;
    
    		return newHead;
    	}
    }
    

Log in to reply
 

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