Key words: Leetcode 234 Palindromes linked list

palindrome

In Chinese, there are palindromes and couplets, such as “The Buddha of Lingshan, the spirit of Buddha mountain “,” the guest on the natural dwelling, unexpectedly the guest in the sky “, etc., which are wonderful anaphora that conform to the positive reading but are the same. Palindromes are similar to 22, 383, 5445, 12321, whether read from left to right.

Create a list

Because js does not have a linked list such a data structure, to do this problem to declare a linked list node object. Remember what a linked list is? Let me draw a picture of that.

function ListNode(x){
    this.val = x; / / data domain
    this.next = null; / / pointer field
}
Copy the code

To implement A->B->C, connect by assigning the next node to the next property of the current object. Of course, you can also add an automatic method.

var head = new ListNode('A');
var second = new ListNode('B');
head.next = second; 
var third = new ListNode('C');
second.next = third;
Copy the code

In JS, this.val represents the value of the current node, this.next points to the next node, and if this.next is null(an object), this node is the last node in the list.

Print the value in the list, know the relationship between the list and the array, after the array to replace the list, so it is better to write code.

function printListFromTailToHead(head)
{
    let arr = [];
    let start = head;
    while(start){
        arr.push(start.val);
        start = start.next;
    }
    arr // ['A','B','C']
    return arr.reverse(); // ['C','B','A']
}
Copy the code

Judge back to ask the linked list

Original description:

Determine if a linked list is palindromic. Example 1: Input: 1->2 Output: false Example 2: Input: 1->2-> 1 Output: true Advanced: Can you solve this problem with O(n) time complexity and O(1) space complexity?

1. Judge palindrome linked list – double pointer

var isPalindrome = function(head) {
    var arr = [];
    var start = head;
    // convert to array
    while (start) {
        arr.push(start.val);
        start = start.next;
    }
    // The palindrome number of one digit
    if (arr.length === 1) {
        return true;
    }
    / / double pointer
    for (var i = 0,
    j = arr.length - 1; i < j; i++, j--) {
        if(arr[i] ! == arr[j]) {return false; }}return true;
};
Copy the code

2. Judge palindrome list – out stack

var isPalindrome = function(head) {
    var arr = [];
    var start = head;
    // convert to array
    while (start) {
        arr.push(start.val);
        start = start.next;
    }
    // The palindrome number of one digit
    if (arr.length === 1) {
        return true;
    }
    var end = head;
    while(end) {
      if(end.val ! == arr[arr.length- 1]) {
          return false;
      }
      arr.pop(); // Treat the array as a stack
      end = end.next;
    }
Copy the code

Both of these are O(n) time

3. Judge palindrome linked list – fast or slow pointer

Use the characteristics of the fast and slow pointer to find the middle value first, the fast pointer goes two steps, the slow pointer goes one step, when the fast pointer goes through the linked list, the slow pointer just goes to the half of the linked list.

1. A copy of the linked list is required
2. The linked list needs to be reversed so that the Pointers can be reversed

Linked list inversion method

var reverseList = function(head) {
    if(head == null || head.next == null) {return head;
		}
        let res = reverseList(head.next);
        head.next.next = head;
		head.next = null;
        return res;
};
Copy the code

Using recursion, better understand what recursion is

• Recursion: Establish connections in order
• Return: Return is the process of getting results

var isPalindrome = function(head) {
    if(! head) {return true;
    }
    var fast = head;
    var slow = head;

    while (fast.next && fast.next.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    var rev = reverseList(slow);
    while(rev ! = =null&& head ! = =null) {
        if(head.val ! == rev.val) {return false;
        }
        rev = rev.next;
        head = head.next;
    }
    return true;
};
Copy the code

O(0) time complexity

other

Related questions about linked lists

1. How to determine if a linked list has a ring?
2. How do I know the length of the ring?
3. How do you find out where the rings join?
4. What’s the length of a linked list?