At the end of the exam, the average score of the class only got the second grade, the teacher in charge then asked: everyone knows the world’s first peak Qomolangma, anyone know the world’s second peak is what? Just as the teacher was going to continue to speak, he heard a voice in the corner: “K2”

preface

# 2018.11.6 clock

Tomorrow’s topic: leetcode-cn.com/problems/re… After tomorrow’s topic extraction announced ha, because some friends want to do in advance ~

The title

Leetcode234 – Palindrome Linked list Chinese link: leetcode-cn.com/problems/pa… English linked list: leetcode.com/problems/pa… Classification: linked list

Detailed questions

Determine if a linked list is palindromic.

Example 1:

Input: 1->2 Output: false Example 2:

Input: 1->2->2->1 Output: true

The title,

One test case away from AC wrong thinking

  • The solution to a palindrome list is to multiply each element of the list by 1,2,3,4… I have a sum sum1;
  • And then you reverse the list, reverse the list just did yesterday, just use the code, get the reverse list;
  • And then for the reversed list, iterate through and multiply each element by 1,2,3,4… I have a sum sum2;
  • And then compare these two sums, and if they’re equal, it’s a palindrome list

code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public boolean isPalindrome(ListNode head) {
        int sum1 = 0;
        if(head == null || head.next == null)
            return true;
        int count = 1;
        ListNode temp = head;
        while(temp ! =null)
        {
            sum1 += count * temp.val;
            count += 1;
            temp = temp.next;
        }
        int sum2 = 0;
        count = 1;
        head = reverseList(head);
        temp = head;
        while(temp ! =null)
        {
            sum2 += count * temp.val;
            count += 1;
            temp = temp.next;
        }
        if(sum1 == sum2)
            return true;
        return false;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode pre = head;
        ListNode pNode = head.next;
        ListNode next = head;
        // Process the first two nodes first;
        pre.next = null;
        while(pNode ! =null)
        {
            next = pNode.next;
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        returnpre; }}Copy the code

As a result, one use case failed, indicating that this method is still a bit of a problem ~~~~

Right train of thought

  • Because the time complexity is O(n) and the space complexity is O(1), the new space cannot be used;
  • The idea is to reverse the list, but not the whole list, but the second half of the list;
  • The second part of the list is reversed, and then one is iterated from the beginning, one is iterated from the tail, and then the value of each node is compared. If the value of each node is the same, the value of each node is continued. If the value of each node is different, the value of each node is returned as false.

code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null)
            return true;
        int length = 0;
        ListNode temp = head;
        while(temp ! =null)
        {
            length++;
            temp = temp.next;
        }
        int halfLength = length / 2;
        temp = head;
        for(int i=0; i<halfLength; i++) temp = temp.next; ListNode pre = temp; ListNode pNode = temp.next; ListNode next = pNode;while(pNode ! =null)
        {
            next = pNode.next;
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        for(int i=0; i<halfLength; i++) {if(head.val ! = pre.val)return false;
            head = head.next;
            pre = pre.next;
        }
        return true; }}Copy the code

The code on

  • 15 to 20 lines, traversing the list, finding a value that is half the length of the list
  • Lines 22-23, find the middle node of the list
  • 24-33 rows reverse linked list
  • Lines 34-40, one from the head and one from the tail, compare values for equality, and return false if they are not equal
  • Finally, return true

conclusion

# 2018.11.6 clock

Author Chogory experienced the autumn recruitment of 2019. He is a computer master of Harbin Institute of Technology and a Java engineer admitted to Baidu. Welcome to follow my wechat public account: Programmer Chogory.