24 Switch nodes in the linked list in pairs
Given a linked list, swap adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, you need to actually swap nodes.
Example: Given 1->2->3->4, you should return 2->1->4->3.Copy the codeLink: leetcode-cn.com/problems/sw…
1. (Iteration)
I have three Pointers to the previous one, the first one to swap, the second one to swap, and then I do the swap and then I go back, and if it’s an even number of nodes first will be Null, and if it’s an odd number of nodes second will be Null. The first two nodes are to be dealt with exclusively (a dummy node is also possible)
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { if(head === null || Next === null) return head; let pre = null; // let first = head; // let second = first.next; // The second node to swap while(second! = null){if(pre === null){first. Next = second. Next; second.next = first; head = second; }else{ pre.next = second; first.next = second.next; second.next = first; } first = first.next; If (first === null)// Only even number of nodes break; pre = second.next; second = first.next; //second===null;} return head; };Copy the code2. (Recursively)
The recursive method is to divide all the nodes of the linked list into two groups, so the function of recursion is to return the first node after the exchange, so in recursion, we can only solve the exchange problem of the internal two nodes.
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { if(head === null || Next === null) return head; let after = head.next; head.next = swapPairs(after.next); Next = head; return after; Return the first of the two};Copy the code203 Remove a linked list element
Deletes all nodes in the linked list that are equal to the given value val.
Example: input: 1 - > 2 - > 6 - > 3 - > 4 - > 5 - > 6, val = 6 output: 1 - > 2 - > 3 - > 4 - > 5Copy the codeLeetcode-cn.com/problems/re…
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { let dummy = new ListNode(0,head); // set a dummy node let pre = dummy; while(pre.next ! = null){ let cur = pre.next; if(cur.val === val) pre.next = cur.next; else pre = pre.next; } return dummy.next; };Copy the code2 Add the two numbers
Give two non-empty linked lists to represent two non-negative integers. Their respective bits are stored in reverse order, and each node can store only one digit. If we add these two numbers together, a new linked list is returned to represent their sum. You can assume that neither of these numbers will start with 0, except for the number 0.
Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Cause: 342 + 465 = 807 Input: L1 = [0], L2 = [0] Output: [0] Input: ,9,9,9,9,9,9 l1 = [9], l2 =,9,9,9 [9] output:,9,9,9,0,0,0,1 [8]Copy the codeLink: leetcode-cn.com/problems/ad…
Their thinking
Use the variable res to represent the carry, add the corresponding numbers, and then add the carry to calculate. The important thing to note here is that if the two lists are not equal in length, then the rest of the list has to be computed; If the last carry is not zero, an additional node is required to store the carry.
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { let res = 0; Let pre = new ListNode(0,null); let newhead = pre; While (l1 | | l2 | | res) {/ / in the final res to 0 will not continue to add a node let a =! l1 ? 0 : l1.val; let b = ! l2 ? 0 : l2.val; let sum = a + b + res; res = Math.floor(sum/10); Sum = sum - res * 10; let cur = new ListNode(sum,null); Pre.next = cur; pre = pre.next; l1 = l1? l1.next : null; l2 = l2? l2.next : null; } return newhead.next; };Copy the code19 Delete the penultimate node of the linked list
Given a linked list, delete the NTH last node of the list and return the first node of the list.
Example: Given a linked list: 1->2->3->4->5, and n = 2. When the penultimate node is deleted, the linked list becomes 1->2->3->5. Note: the given n is guaranteed to be valid.Copy the codeLink: leetcode-cn.com/problems/re…
Thinking analytical
The fast and slow Pointers are used. The fast Pointers and the slow Pointers are separated by n and then traversed together. When the fast Pointers reach the end, the slow Pointers just point to the deleted node. (Again, a BRE pointer is used to point to the previous node of the deleted node for easy deletion.)
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { let dummy = new ListNode(0,head); let bre = dummy; // let cur = head; // let pre = head; While (--n) pre = pre.next; while(pre.next){ pre = pre.next; cur = cur.next; bre = bre.next; } bre.next = cur.next; return dummy.next; };Copy the code206 Reverse linked lists
Reverse a single linked list.
Example: input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL output: 5 - > 4 - > 3 - > 1 - > 2 - > NULLCopy the codeLink: leetcode-cn.com/problems/re…
Their thinking
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let pre = null; let cur = head; while(cur ! = null){ let next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; };Copy the code92. Reverse linked list II
Inverts the linked list from position m to n. Use a scan to complete the inversion.
Description: 1 ≤ M ≤ N ≤ The length of the linked list. Example: input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL, m = 2, n = 4 output: 1 - > > 4-3 - > 2 - > 5 - > NULLCopy the codeTheir thinking
Partial inversion needs to record four positions, namely M-1, M, N, and N +1, so that normal connection can be made with other nodes after the inversion [m,n]. The reverse section borrows the code from the previous problem and changes the return value slightly.
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */ var reverseBetween = function(head, m, n) { let sliceStart = null; // let sliceEnd = null; // let pre = null; // let tail = null; // let count = 1; let cur = head; while(count <= n){ if(count === m-1){ pre = cur; } if(count === m){ sliceStart = cur; } if(count === n){ sliceEnd = cur; } cur = cur.next; count++; } tail = sliceEnd.next; sliceEnd.next = null; [sliceStart,sliceEnd] = reverseList(sliceStart); if(pre){ pre.next = sliceStart; }else{ head = sliceStart; } sliceEnd.next = tail; return head; }; var reverseList = function(head) { let pre = null; let cur = head; while(cur ! = null){ let next = cur.next; cur.next = pre; pre = cur; cur = next; } return [pre,head]; };Copy the code