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