“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Title 1

Flip linked lists in groups of 52. K

Give you the head of a linked list, rotate the list, and move each node k positions to the right.

Example 1:

Input: head = [1,2,3,4,5], k = 2 output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4

Tip:

The number of nodes in the linked list is in the range [0, 500] \

  • -100 <= Node.val <= 100

0 <= k <= 2 * 109

Ask questions

  • What happens when k moves more than the length of the list?
  • How do I rotate the list?

Analysis of the

  • Define a pre pointer and initialize it to point to the list head node head.

  • Make the last node of the list point to the node pointed to by the pre pointer.

  • makepreMove the pointer back one time

  • repeatkThe above operations

  • Make the node to which the pre pointer points pointnull.

  • Tidy it up

  • So the question is, whenkGreater than or equal to the list lengthlengthWhat do I do
  • whenkIs equal to the length of the listlengthWhen, that is to say, it goes exactly the same way around and comes back to the original head node.
  • In other words, doingk%lengthCircle.

Code implementation

/** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var rotateRight = function(head, k) { if(! head) return null let pre = head let size = 1 while(pre.next){ pre = pre.next size ++ } pre.next = head for(let i = 0; i<size-k%size-1; i++){ head = head.next } pre = head.next head.next = null return pre };Copy the code

Topic 2

Switch nodes in a linked list in pairs

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

Example 1:

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

Example 2:

Input: head = [] Output: []

Example 3:

Input: head = [1] Output: [1]

Tip:

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

Advanced:

Can you solve this problem without changing the list node values? (That is, only the node itself is modified.)

Analysis of the

Create a virtual head node that points to the head in the list

We define a temp pointer that points to the virtual head node and we define a pre pointer that points to the node next to the temp pointer and we define a cur pointer that points to the node next to the node that the Pre pointer points to

Make the node that Pre points to point to the next node that cur points to point to the node that Pre points to

So temp goes to cur and pre goes to the next node that’s cur and pre goes to the next node that’s cur

Continue pointing to the above operations

Repeat until pre or cur points to null

Tidy it up

Code implementation

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let ret = new ListNode(-1,head)
    let temp = ret
    while(temp.next&&temp.next.next){
        let pre = temp.next
        let cur = temp.next.next
        pre.next = cur.next
        cur.next = pre
        temp.next = cur
        temp = pre
    }
    return ret.next
};
Copy the code