24. 兩兩交換鏈表中的節點
給定一個鏈表，兩兩交換其中相鄰的節點，并回傳交換后的鏈表，
你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，
示例:
給定 1->2->3->4, 你應該回傳 2->1->4->3.
解題：我們定義4個指標如上進行節點交換，
1.給head添加一個虛擬頭節點thead
2.定義4個指標 p， node1， node2， next 我們需要將p.next ->node2 node1.next -> next node2.next ->node1 完成以后將 p指標移動到node1
3.我們需要判斷 p.next 和p.next.next 都不為空，這樣next 最差為null 不會越界
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { let thead = new ListNode(0); thead.next = head; let p = thead; while(p.next != null && p.next.next != null){ let node1 = p.next; let node2 = node1.next;
let next = node2.next
p.next = node2; node1.next = next; node2.next = node1; p = node1; } return thead.next; };
237. 洗掉鏈表中的節點
請撰寫一個函式，使其可以洗掉某個鏈表中給定的（非末尾）節點，你將只被給定要求被洗掉的節點，
現有一個鏈表 -- head = [4,5,1,9]，它可以表示為:
示例 1:
輸入: head = [4,5,1,9], node = 5 輸出: [4,1,9] 解釋: 給定你鏈表中值為 5 的第二個節點，那么在呼叫了你的函式之后，該鏈表應變為 4 -> 1 -> 9.
解題：
1.我們無法直接洗掉給定的節點，我們只能拿到給定節點的下一個節點的值，
2.我們用該節點的下一個節點的值覆寫當前節點的值，然后洗掉下一個節點，即相當于實作了對該節點的洗掉
3.我們處理node 為null和node.next為null的特殊情況
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} node * @return {void} Do not return anything, modify node in-place instead. */ var deleteNode = function(node) { if(node == null){ return } if(node.next == null){ delete node node = null return } node.val = node.next.val node.next = node.next.next };
19. 洗掉鏈表的倒數第N個節點
給定一個鏈表，洗掉鏈表的倒數第 n 個節點，并且回傳鏈表的頭結點，
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2. 當洗掉了倒數第二個節點后，鏈表變為 1->2->3->5.
解題：
1.給head設定虛擬頭節點
2.設定fast 和show兩個指標
3.fast指標先移動n位，然后fast指標和show指標同時移動
4.當fast指標為空時，show.next節點即為需要洗掉的節點，我們把show.next ->show.next.next
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { let preHead = new ListNode(0) preHead.next = head let fast = preHead, slow = preHead // 快先走 n+1 步 while(n--) { fast = fast.next } let i = 0 // fast、slow 一起前進 while(fast && fast.next) { slow = slow.next fast = fast.next } slow.next = slow.next.next return preHead.next };
鏈表的js演算法就先介紹到這里了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/28125.html
標籤：JavaScript