Title link: 234. Palindrome linked list

Title description:

Determine if a linked list is palindromic.

Example 1:
Input: 1->2 Output: falseCopy the code
Example 2:
Input: 1->2->2->1 Output: trueCopy the code

Directions: For this part,

It’s easy to understand, and there are many solutions. It’s easy to determine whether a palindrome is a palindrome, but it’s much harder to operate on a linked list because neither forward nor reverse access is O(1). Copying a list value to an arraylist is O(n), so the easiest way to do this is to copy a list value to an arraylist and use a double pointer.

Array solution idea:

First it iterates through, putting the value into an array, and then using a double pointer to determine whether it is palindrome.

Array solution code implementation:

func isPalindrome(head *ListNode) bool { vals := []int{} for head ! = nil { vals = append(vals, head.Val) head = head.Next } start, end := 0, len(vals)-1 for start < end { if vals[start] ! = vals[end] { return false } start++ end-- } return true }Copy the code

Dual-pointer train of thought:

  1. Define fast and slow double Pointers
  2. Key point: find mid, the fast pointer advances 2 steps, the slow pointer advances 1 step, and finally the loop ends and the slow pointer is the intermediate value
  3. Reverse the second half with mid as head
  4. The first and second Val values are compared, and any mismatches are returned immediately

Double pointer solution code implementation:

Func isPalindrome(head *ListNode) bool {// Define fast, slow := head, head After loop the slow pointer is extremely mid for fast! = nil && fast.Next ! Next fast = fast.next.Next} var pre, current *ListNode = nil, slow for current! Next = pre pre = current current = temp = nil {temp := current.Next = pre pre = current current = temp} Return false for pre! = nil { if pre.Val ! = head.Val { return false } pre = pre.Next head = head.Next } return true }Copy the code

Conclusion:

It is also a simple problem, the problem can also be solved by recursive thinking, interested partners can try.