Switching nodes in a paironed list (Question number 24)

The title

Given a linked list, swap the adjacent nodes in pairs and return the swapped list.

You can’t just change the values inside a node, but actually switch nodes.

Example 1:

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

Example 2:

Input: head = []Copy the code

Example 3:

Input: head = [1]Copy the code

Tip:

  • The number of nodes in the list is in the range [0, 100]
  • 0 <= Node.val <= 100

link

Leetcode-cn.com/problems/sw…

explain

This problem is ok, according to the reverse chain list written yesterday, using the recursive method to operate, nothing to say, mainly is a better answer, here is the iteration, anyway, I am not too understand, later have time to see

My own solution

var swapPairs = function(head) { if (! head || ! head.next) return head var dummy = head.next if (dummy.next) dummy.next = swapPairs(dummy.next) head.next = dummy.next dummy.next = head head = dummy return head };Copy the code

A better answer

var swapPairs = function(head) { // 1. Verify that head is greater than or equal to two, otherwise return; if (! head || ! head.next) return head; // 2. Create list sentry header and create pointer curr; let res = new ListNode(null); res.next = head; let prev = res; Console. log(prev) // 3. Start loop // // 3.2 Sentry -> SND, FST -> SND. Curr = curr.next. Next; while (prev.next && prev.next.next) { let [fst, snd] = [prev.next, prev.next.next]; [prev.next, fst.next, snd.next] = [snd, snd.next, fst]; prev = prev.next.next; } // 4. Return res.next; return res.next; };Copy the code

Ring linked list (Question No. 141)

The title

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list. Returns true if there is a loop in the list. Otherwise, return false.

Advanced:

  • Can you solve this problem with O(1) (i.e., constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: trueCopy the code

Example 2:

Input: head = [1,2], pos = 0 output: true explanation: there is a loop in the list with the end connected to the first node.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: false Description: There is no loop in the linked list.Copy the code

Tip:

  • The number of nodes in the list ranges from [0, 104]
  • -105 <= Node.val <= 105
  • Pos is -1 or a valid index in the list.

link

Leetcode-cn.com/problems/li…

explain

If it is a loop, it will report an error, and then catch the error. Very simple and convenient, but the performance is worrying, only more than 5% of the people.

The second solution is more normal. It iterates, putting the next of each node in the Map, and then starts the loop. If the node already exists in the Map, then the loop has been proved.

Better solution is actually a double pointer iteration, the first is in fact more similar to the operation of the single needle, is simply two people running, a person, the first trigger after another, if it is a circle, then start people will inevitably encounter before they set out, also it is more than the first one was a circle.

The second better solution is double pointer, two people start at the same time, one person runs faster, the other person runs slower, is a small optimization of the last method, looks more concise, run faster.

My own solution 1

var hasCycleSpecial = function(head) { try { JSON.stringify(head) return false } catch(err) { return !! err } };Copy the code

My own solution 2

var hasCycle = function(head) { if (! head || ! head.next) return false var res = head; var obj = new Map var ans = false while (res) { if (obj.has(res)) { ans = true res = null } else { obj.set(res, 1) res = res.next } } return ans };Copy the code

Better answer 1

var hasCycle = function(head) { if (! head || ! head.next) return false var fast = head.next var slow = head while (fast ! == slow) { if (! fast || ! fast.next) { return false } fast = fast.next.next slow = slow.next } return true };Copy the code

Better answer 2

var hasCycle4 = function (head) {
  var slow = head,
    fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow == fast) return true
  }
  return false
}
Copy the code




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ