206. 反轉鏈表

反轉一個單鏈表。

示例：

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解法：

var reverseList = function(head) {let cur = head, prev = nullwhile(cur) {[cur.next, prev, cur] = [prev, cur, cur.next]}return prev }; 復制代碼

思路分析：prev保存前一個節點， 主要邏輯分三步：

修改cur的next，指向前一個節點，即prev

保存當前節點cur為prev，供下一個節點使用

移動當前節點指針cur到下一個節點cur.next

24. 兩兩交換鏈表中的節點

給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例：

給定 1->2->3->4, 你應該返回 2->1->4->3.

解法一：

var swapPairs = function(head) {let node = new ListNode(0) //新建一個節點，用于保存head節點node.next = headlet prev = nodewhile(prev.next && prev.next.next) {let a = prev.nextlet b = a.nextprev.next = a.nexta.next = b.nextprev = b.next = a}return node.next }; 復制代碼

解題思路： 定義一個新的頭節點node,將頭節點next指向head，定義prev, a, b分別指向前三項，第一遍循環如下圖：

循環過程中node始終指向自定義的頭結點，而node.next即為真正的頭節點。
遍歷第二遍時，a, b分別指向3，4，執行流程同上，執行完第二遍即結束循環。

解法二：

var swapPairs = function(head) {if(!head) return nullif(!head.next) return headlet temp = head.nexthead.next = swapPairs(temp.next)temp.next = headreturn temp }; 復制代碼

解題思路：主要邏輯是head.next指向遞歸返回的上一個temp,同時修改temp.next為head,實現后一個節點指向前一個節點，同時前一個節點指向遞歸返回的節點，最后swapPairs接收到的就是最后返回的temp，即第二個節點2.

141. 環形鏈表

給定一個鏈表，判斷鏈表中是否有環。

示例：

輸入：head = [3,2,0,-4], 輸出：true

解法一：使用快慢指針，快指針每次走兩步，慢指針每次走一步，如果有環，二者必定會碰到一起；

var hasCycle = function(head) {let fast = slow = headwhile(fast && slow && fast.next) { //fast.next不存在說明鏈表已走完slow = slow.nextfast = fast.next.nextif(fast === slow) {return true}}return false }; 復制代碼

解法二：使用Set保存每個節點的地址，如果有環，Set里元素必定會重復；

var hasCycle = function(head) {let set = new Set()while(head) {if(set.has(head)) return trueset.add(head)head = head.next}return false }; 復制代碼

142. 環形鏈表 II

給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null

示例：

輸入：head = [3,2,0,-4]
輸出：tail connects to node index 1

解法一：

var detectCycle = function(head) {let set = new Set()let cur = headwhile(cur) {if(set.has(cur)) return curset.add(cur)cur = cur.next}return null }; 復制代碼

解題思路：用Set保存每次遍歷的地址，遍歷時發現地址重復即為入口節點

解法二：

var detectCycle = function(head) {let fast = slow = headwhile(slow && fast && fast.next) {slow = slow.nextfast = fast.next.nextif(slow === fast) {slow = headwhile(slow !== fast) {slow = slow.nextfast = fast.next}return fast}}return null }; 復制代碼

解題思路：

先用快慢指針方法確定鏈表是否有環

如果有環的，慢指針slow重新從head出發，slow,fast每次都走一步，如果重合，重合處必為環的入口;

入口解釋一下：

首先第一次遍歷后假設在C點相遇，此時：

慢指針走的S1 = |AB| + |BC|
快指針走的S2 = 2 * ( |AB| + |BC| )

在另一個角度，S2 走的距離就是 |AB| + |BC| + n * s (s為環的大小),即

快指針走的S2 = |AB| + |BC| + n * s

所以可以得到

2 * ( |AB| + |BC| ) = |AB| + |BC| + n * s
可以得到：|AB| = n * s - |BC|

可以看出如果slow從A點開始，fast從相遇點C開始，兩者以同樣速度必會在B點相遇

總結

以上是生活随笔為你收集整理的leetcode题目解析(js)--链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。