Leetcode234 question - simple method to judge palindrome linked list

Catalog

subject

analysis

Code implementation

---

subject

Give you the head node of a single linked list head , Please judge whether the linked list is a palindrome linked list . If it is , return true ; otherwise , return false .

Tips :
The number of nodes in the linked list is in the range [1,105] Inside ,0<= Node.val <= 9
requirement ：

Time complexity ：O(n)

Spatial complexity ：O(1)

analysis

To meet the requirements of complexity , We can reverse the sub linked list starting from the intermediate node , Compare the sub linked list with the original linked list , Judge whether it is palindrome list .（ At this time, there is no new linked list node , They are all operated on the basis of the original linked list ）

---

First step ： Find the middle node of the linked list

// Find the middle point 
public ListNode middleNode(ListNode head) {
    ListNode f = head;
    ListNode l = head;
    while (f != null && f.next != null) {
        f = f.next.next;
        l = l.next;
    }
    return l;
}

 

---

 

The second step ： Reverse the sub linked list starting from the intermediate node

// reverse 
public ListNode reverList(ListNode head) {
    if(head ==null||head.next ==null){
        return head;
    }
    ListNode prev = null;
    ListNode cur = head;
    while(cur !=null){
        ListNode next = cur.next;
        cur.next = prev;// Broken wire 
        prev = cur;
        cur = next;
    }
    return prev;
}

---

The third step ： Compare the values of the original linked list and the sub linked list

Traverse and compare the original linked list and sub linked list

// Ergodic comparison 
public boolean isPalindrome(ListNode head) {
    ListNode midHead = middleNode(head);
    ListNode newHead = reverList(midHead);
    while (newHead != null) {
        if (head.val != newHead.val) {
        return false;
    }
    newHead = newHead.next;
    head  = head.next;
    }
    return true;
}

Code implementation

The three-step method is combined to solve the problem

class Solution {
    // Ergodic comparison 
    public boolean isPalindrome(ListNode head) {
        ListNode midHead = middleNode(head);
        ListNode newHead = reverList(midHead);
        while (newHead != null) {
            if (head.val != newHead.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }
    // reverse 
    public ListNode reverList(ListNode head) {
        if(head ==null||head.next ==null){
            return head;
        }
        ListNode prev = null;
        ListNode cur = head;
        while(cur !=null){
            ListNode next = cur.next;
            cur.next = prev;// Broken wire 
            prev = cur;
            cur = next;
        }
        return prev;
    }
    // In the middle 
    public ListNode middleNode(ListNode head) {
        ListNode f = head;
        ListNode l = head;
        while (f != null && f.next != null) {
            f = f.next.next;
            l = l.next;
        }
        return l;
    }
}

​

Time complexity ：O(n).

Spatial complexity ：O(1).