<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 0206. 反轉鏈表 ## 題目地址(206. 反轉鏈表) <https://leetcode-cn.com/problems/reverse-linked-list/> ## 題目描述 反轉一個單鏈表。 ``` <pre class="calibre18">``` 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 進階: 你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題? ``` ``` ## 前置知識 - [鏈表](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 百度 - 騰訊 - adobe - amazon - apple - bloomberg - facebook - microsoft - snapchat - twitter - uber - yahoo - yelp - zenefits ## 思路 這個就是常規操作了,使用一個變量記錄前驅 pre,一個變量記錄后繼 next. 不斷更新`current.next = pre` 就好了 ## 關鍵點解析 - 鏈表的基本操作(交換) - 虛擬節點 dummy 簡化操作 - 注意更新 current 和 pre 的位置, 否則有可能出現溢出 ## 代碼 語言支持:JS, C++, Python,Java JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode} head * @return {ListNode} */</span> <span class="hljs-keyword">var</span> reverseList = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">head</span>) </span>{ <span class="hljs-keyword">if</span> (!head || !head.next) <span class="hljs-keyword">return</span> head; <span class="hljs-keyword">let</span> cur = head; <span class="hljs-keyword">let</span> pre = <span class="hljs-params">null</span>; <span class="hljs-keyword">while</span> (cur) { <span class="hljs-keyword">const</span> next = cur.next; cur.next = pre; pre = cur; cur = next; } <span class="hljs-keyword">return</span> pre; }; ``` ``` C++ Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">reverseList</span><span class="hljs-params">(ListNode* head)</span> </span>{ ListNode* prev = <span class="hljs-params">NULL</span>; ListNode* cur = head; ListNode* next = <span class="hljs-params">NULL</span>; <span class="hljs-keyword">while</span> (cur != <span class="hljs-params">NULL</span>) { next = cur->next; cur->next = prev; prev = cur; cur = next; } <span class="hljs-keyword">return</span> prev; } }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for singly-linked list.</span> <span class="hljs-title"># class ListNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.next = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverseList</span><span class="hljs-params">(self, head: ListNode)</span> -> ListNode:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> head: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> prev = <span class="hljs-keyword">None</span> cur = head <span class="hljs-keyword">while</span> cur: cur.next, prev, cur = prev, cur, cur.next <span class="hljs-keyword">return</span> prev ``` ``` Java Code: ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> ListNode <span class="hljs-title">reverseList</span><span class="hljs-params">(ListNode head)</span> </span>{ ListNode pre = <span class="hljs-keyword">null</span>, cur = head; <span class="hljs-keyword">while</span> (cur != <span class="hljs-keyword">null</span>) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } <span class="hljs-keyword">return</span> pre; } } ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) ## 拓展 通過單鏈表的定義可以得知,單鏈表也是遞歸結構,因此,也可以使用遞歸的方式來進行 reverse 操作。 > 由于單鏈表是線性的,使用遞歸方式將導致棧的使用也是線性的,當鏈表長度達到一定程度時,遞歸會導致爆棧,因此,現實中并不推薦使用遞歸方式來操作鏈表。 1. 除第一個節點外,遞歸將鏈表 reverse 2. 將第一個節點添加到已 reverse 的鏈表之后 > 這里需要注意的是,每次需要保存已經 reverse 的鏈表的頭節點和尾節點 C++實現 ``` <pre class="calibre18">``` <span class="hljs-title">// 普通遞歸</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">reverseList</span><span class="hljs-params">(ListNode* head)</span> </span>{ ListNode* tail = <span class="hljs-params">nullptr</span>; <span class="hljs-keyword">return</span> reverseRecursive(head, tail); } <span class="hljs-function">ListNode* <span class="hljs-title">reverseRecursive</span><span class="hljs-params">(ListNode *head, ListNode *&tail)</span> </span>{ <span class="hljs-keyword">if</span> (head == <span class="hljs-params">nullptr</span>) { tail = <span class="hljs-params">nullptr</span>; <span class="hljs-keyword">return</span> head; } <span class="hljs-keyword">if</span> (head->next == <span class="hljs-params">nullptr</span>) { tail = head; <span class="hljs-keyword">return</span> head; } <span class="hljs-keyword">auto</span> h = reverseRecursive(head->next, tail); <span class="hljs-keyword">if</span> (tail != <span class="hljs-params">nullptr</span>) { tail->next = head; tail = head; head->next = <span class="hljs-params">nullptr</span>; } <span class="hljs-keyword">return</span> h; } }; <span class="hljs-title">// (類似)尾遞歸</span> <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function">ListNode* <span class="hljs-title">reverseList</span><span class="hljs-params">(ListNode* head)</span> </span>{ <span class="hljs-keyword">if</span> (head == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> head; <span class="hljs-keyword">return</span> reverseRecursive(<span class="hljs-params">nullptr</span>, head, head->next); } <span class="hljs-function">ListNode* <span class="hljs-title">reverseRecursive</span><span class="hljs-params">(ListNode *prev, ListNode *head, ListNode *next)</span> </span>{ <span class="hljs-keyword">if</span> (next == <span class="hljs-params">nullptr</span>) <span class="hljs-keyword">return</span> head; <span class="hljs-keyword">auto</span> n = next->next; next->next = head; head->next = prev; <span class="hljs-keyword">return</span> reverseRecursive(head, next, n); } }; ``` ``` JavaScript 實現 ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> reverseList = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">head</span>) </span>{ <span class="hljs-title">// 遞歸結束條件</span> <span class="hljs-keyword">if</span> (head === <span class="hljs-params">null</span> || head.next === <span class="hljs-params">null</span>) { <span class="hljs-keyword">return</span> head; } <span class="hljs-title">// 遞歸反轉 子鏈表</span> <span class="hljs-keyword">let</span> newReverseList = reverseList(head.next); <span class="hljs-title">// 獲取原來鏈表的第 2 個節點 newReverseListTail</span> <span class="hljs-keyword">let</span> newReverseListTail = head.next; <span class="hljs-title">// 調整原來頭結點和第 2 個節點的指向</span> newReverseListTail.next = head; head.next = <span class="hljs-params">null</span>; <span class="hljs-title">// 將調整后的鏈表返回</span> <span class="hljs-keyword">return</span> newReverseList; }; ``` ``` Python 實現 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">reverseList</span><span class="hljs-params">(self, head: ListNode)</span> -> ListNode:</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> head <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> head.next: <span class="hljs-keyword">return</span> head ans = self.reverseList(head.next) head.next.next = head head.next = <span class="hljs-keyword">None</span> <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) ## 相關題目 - [92.reverse-linked-list-ii](92.reverse-linked-list-ii.html) - [25.reverse-nodes-in-k-groups](25.reverse-nodes-in-k-groups-cn.md) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看