======アルゴリズム======

LeetCode C ++ 206。逆リンクリスト【LinkedList】【リンクリスト逆】



Leetcode C 206 Reverse Linked List Linkedlist Linked List Reverse



逆に 単独で リンクリスト。

例：



Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

ファローアップ：

  • リンクリストはどちらかを逆にすることができます 反復的または再帰的に。 両方を実装できますか？

質問：単一リンクリストを逆にします。再帰的または反復的である可能性があります。



問題解決方法1：反復（ヘッド補間）

単一リンクリストを逆にすることは、元の単一リンクリストから開始することと同じです。 新しいリンクリストの先頭からノードを順番に挿入します 、つまり、ヘッド挿入方式です。

  • 実行時間：8ミリ秒、すべてのC ++送信でユーザーの80.47％を打ち負かしました
/** * Definition for singly-linked list. * struct ListNode { * int val * ListNode *next * ListNode(int x) : val(x), next(NULL) {} * } */ class Solution { public: ListNode* reverseList(ListNode* head) { //iteratively reversed head interpolation if (head == NULL || head->next == NULL) return head //Empty table/An ​​element is returned directly ListNode *newHead = new ListNode(0) //The new linked list head node does not move, head is the pointer of the original linked list head while (head) { ListNode *t = head->next head->next = newHead->next //cur points to the original first node newHead->next = head //The node pointed to by cur becomes the new first node head = t } return newHead->next } }

ヘッドノードを変更せずに、新しい単一リンクリストを作成する方法は次のとおりです。

class Solution { public: ListNode* reverseList(ListNode* head) { //iteratively reversed if (head == NULL || head->next == NULL) return head //Empty table/An ​​element is returned directly ListNode *newHead = NULL //New linked list head pointer, original linked list head while (head) { //The head pointer of the new linked list keeps changing until it points to the end node of the original linked list ListNode *t = head->next //Save the pointer to the original linked list head->next = newHead //These two sentences turn the head node of the original linked list into the head node of the new linked list newHead = head head = t //Process the header node of the next original linked list } return newHead } }

問題解決方法2：再帰

再帰の境界を見つけるだけで、元のリンクリストの最後（つまり、新しいリンクリストのヘッドノード）へのポインタを返し、ノードを後ろから前に逆にします。 単一リンクリストの反転 それはほとんど書かれている通りです。



  • 実行時間：8ミリ秒、すべてのC ++送信でユーザーの80.47％を打ち負かしました
class Solution { public: ListNode* reverseList(ListNode* head) head->next == NULL) //Recursion boundary return head //Empty table/An ​​element is returned directly ListNode *newHead = reverseList(head->next) //Reverse the head node of the linked list, unchanged head->next->next = head //Reverse the linked list to expand the new node head->next = NULL //Reverse the end of the linked list return newHead }