This is the 9th day of my participation in the wenwen Challenge

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

114. Palindrome-linked-list

The label

  • The list
  • simple

The title

Leetcode portal

Let’s just open leetCode.

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

The basic idea

  1. Copy the linked list values into the arraylist.
  2. Determine whether it is palindrome.

Writing implement

var isPalindrome = function(head) {
  // Prepare an array to store the list values
  let compareArr = []
  // Loop the list into the array
  while(head ! = =null) {
    compareArr.push(head.val)
    head = head.next
  }
  // Check the array palindrome
  return compareArr.join(' ') === compareArr.reverse().join(' ')}Copy the code

More efficient use of dual Pointers

var isPalindrome = function(head) {
    const vals = [];
    while(head ! = =null) {
        vals.push(head.val);
        head = head.next;
    }
    // Double pointer judgment palindrome
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if(vals[i] ! == vals[j]) {return false; }}return true;
};
Copy the code

115. Sort list (sort-list)

The label

  • The list
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given the head of your list, please sort it in ascending order and return the sorted list.

Advanced: Can you sort linked lists in O(n log n) time complexity and constant space complexity?

Example 1:

Input: head = [4,2,1,3] output: [1,2,3,4]Copy the code

Example 2:

Input: head = [-1,5,3,4,0]Copy the code

The basic idea

If you’re not familiar with merge sort, take a look at my article [Algorithm Unpacking] merge sort

And that’s exactly what we need to do, along with the divide-and-conquer idea that we talked about last time

According to the time complexity of the problem, violence is definitely not effective. We can use the decomposition of this complex problem into

  1. Let’s break up the big list

    • The process of dividing until there is no more dichotomy, that is, the stack is pushed recursively until there is only one node in the chain (ordered), and then it is merged recursively out of the stack.

    • The binary method is to find the midpoint of the linked list and divide the linked list into two sub-linked lists with the midpoint as the boundary. To find the midpoint of the linked list, the fast pointer moves 2 steps at a time, and the slow pointer moves 1 step at a time (similar to the idea of circular lists). When the fast pointer reaches the end of the linked list, the slow pointer points to the list node as the midpoint of the linked list.

  2. Merge the two ordered lists

    • In the process of merging, the merged result is returned to the parent call, layer by layer, and finally comes to the answer to the big question.
    • Merging two ordered lists we’ve done this before, so in fact, a lot of difficult problems are merging simple problems, and all you have to do is disassemble them. This ability requires considerable accumulation.

Writing implement

We can give you a pseudo-code idea

var sortList = function(head) {
    // Binary (recursive)L = sortList(left chain)// Sorted left chainR = sortList(right chain)// Sorted right chain
    merged = mergeList(l, r) // Merge
    // Returns the merged result to the parent call
    return merged
};
Copy the code

Next, complete the logic, don’t be afraid to look like code, in fact, the idea is very clear

// Merge two ordered lists
var mergeTwoLists = function(l1, l2) {
  // Terminating condition: When both lists are empty, we have merged the lists.
  if (l1 === null) {
    return l2
  } else if (l2 === null) {
    return l1
  } else if (l1.val < l2.val) {
    // The next pointer to the smaller node points to the merge result of the remaining nodes.
    l1.next = mergeTwoLists(l1.next, l2)
    return l1
  } else {
    l2.next = mergeTwoLists(l1, l2.next)
    return l2
  }
};

var sortList = function(head) {
  / / found empty
  if(! head || ! head.next) {return head
  }
  // Fast and slow Pointers to split lists
  let [fast, slow, preSlow] = [head, head, null]
  while (fast && fast.next) {
    // Record the possible break point, which is the current slow position
    preSlow = slow
    // Fast pointer 2 steps, slow pointer 1 step
    fast = fast.next.next
    slow = slow.next
  }
  // Empty the end of the first list
  preSlow.next = null
  // When the fast pointer reaches the end, the current slow pointer is the separator point
  // Recursive operations continue into left and right subchains
  let l = sortList(head)
  let r = sortList(slow)
  return mergeTwoLists(l, r)
};
Copy the code

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference

  • Leetcode-cn.com/problems/so…