Friday, 1 February 2019

LeetCode Q234 Palindrome Linked List

Q234 Palindrome Linked List



Since the ListNode class provided only has a next pointer
 So we have to create a way that we can go backward

 You might think of converting the singly-linked list into an array, but it requires O(n) space

 Solution:
 Create two head points: fast and slow, start to traverse the list, fast always go to the next next node, slow always go to the next
 The aim is to let slow find the start node of the second half
 1 -> 2 -> 3 -> 4
 fast 1  fast 3  fast nil
 slow 1  slow 2  slow 3

 Next make fast point to head again
 We will end up with
 fast 1 -> 2 -> 3 -> 4
 slow 3 -> 4

 Reverse slow, we will have a reversed second half of the list and the origial first half
 slow 4 -> 3
 fast 1 -> 2 -> 3

 Traverse slow and fast at the same time, if all the values listed in slow are the same in fast list, it is a palindrome

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/TwoPointers/Q234PalindromeLinkedList.playground/Contents.swift

No comments:

Post a Comment