連結串列反轉

Harshit Jindal 2023年10月12日
  1. 連結串列反轉演算法
  2. 連結串列反轉圖解
  3. 連結串列反轉的實現
  4. 連結串列反轉演算法複雜度
連結串列反轉

連結串列是線性資料結構。連結串列的一個節點包括:

  • 資料項。
  • 下一個節點的地址。
class Node {
  int data;
  Node *next;
};

連結串列

本文將介紹如何在給定指向連結串列頭節點的指標的情況下反轉連結串列。

連結串列反轉演算法

head 成為連結列表的第一個節點。

迭代演算法

  • 初始化 3 個指標-curr 設定為 headprevnext 設定為 NULL
  • 遍歷連結列表,直到到達最後一個節點,即 curr!=NULL 並執行以下操作:
    • next 設定為 curr->next 個,以將 next 移動到其下一個節點。
    • 通過將當前節點指向 prev 來反轉其方向。因此,將 curr->next 設定為 prev
    • prev 設定為 curr,將其向前移動一個位置。
    • curr 設定為 next,將其向前移動一個位置。

遞迴演算法

  • 將列表分為兩部分:第一個節點,即 head 節點,以及其餘的連結列表。
  • 呼叫 reverse(head->next),即,反向連結列表的其餘部分,並將反向連結列表儲存為 rev
  • head 附加到反向連結列表 rev 的末尾。
  • 指向 head,即反向連結列表的尾部指向 NULL

使用堆疊的反向連結列表

  • 初始化指向連結列表的 head 的指標 curr
  • 遍歷連結串列,並將每個節點一一插入。
  • head 更新到連結串列中的最後一個節點,即堆疊中的第一個節點。
  • 開始一個接一個地從堆疊中彈出節點,並將其附加到反向連結串列的末尾。
  • 將最後一個節點的下一個指標更新為 NULL

連結串列反轉圖解

連結串列反轉

  • 初始化 curr 以指向頭部,即節點 2prev 以及 curr 的資料為 NULL
  • next 指向 curr->next,其值等於 4
  • curr->next 設定為 prev,以獲得以 2 為首的反向連結列表。
  • prev 移至 curr,即資料為 2 的節點,將 curr 移至 next,即資料為 4 的節點。
  • next 指向 curr->next,其值等於 6
  • curr->next 設定為 prev,以獲得以 24 為反向節點,以 4 為首的反向連結串列。
  • prev 移至 curr,即資料為 4 的節點,將 curr 移至 next,即資料為 6 的節點。
  • next 指向 curr->next,其值等於 8
  • curr->next 設定為 prev,以獲得以 246 為反向節點且以 6 為首的反向連結串列。
  • prev 移至 curr,即資料為 6 的節點,將 curr 移至 next,即資料為 8 的節點。
  • next 指向 curr->next,即 NULL
  • curr->next 設定為 prev,以 2468 作為反向節點,以 8 作為頭獲得反向連結串列。
  • prev 移至 curr,即資料為 8 的節點,將 curr 移至 NULL,演算法終止。

連結串列反轉的實現

#include <bits/stdc++.h>
using namespace std;

class Node {
 public:
  int data;
  Node* next;
  Node(int x) {
    this->data = x;
    this->next = NULL;
  }
};

void printList(Node* head) {
  Node* curr = head;
  while (curr != NULL) {
    cout << curr->data << " ";
    curr = curr->next;
  }
}

Node* reverse(Node* head) {
  Node* curr = head;
  Node *prev = NULL, *next = NULL;

  while (curr != NULL) {
    next = curr->next;
    curr->next = prev;
    prev = curr;
    curr = next;
  }
  head = prev;
  return head;
}

Node* recursiveReverse(Node* head) {
  if (head == NULL || head->next == NULL) return head;

  Node* rest = recursiveReverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return rest;
}

void reverseLL(Node** head) {
  stack<Node*> s;
  Node* temp = *head;
  while (temp->next != NULL) {
    s.push(temp);
    temp = temp->next;
  }
  *head = temp;

  while (!s.empty()) {
    temp->next = s.top();
    s.pop();
    temp = temp->next;
  }
  temp->next = NULL;
}

int main() {
  Node* head = new Node(1);
  head->next = new Node(2);
  head->next->next = new Node(3);
  head->next->next->next = new Node(4);
  head->next->next->next->next = new Node(5);
  head->next->next->next->next->next = new Node(6);
  head = reverse(head);
  printList(head);
  cout << "\n";
  head = recursiveReverse(head);
  printList(head);
  cout << "\n";
  reverseLL(&head);
  printList(head);
  cout << "\n";
  return 0;
}

連結串列反轉演算法複雜度

時間複雜度

  • 平均情況

要反轉完整的連結串列,我們必須訪問每個節點,然後將其附加到反轉表。因此,如果一個連結串列具有 n 個節點,則遍歷的平均情況下時間複雜度約為 O(n)。時間複雜度約為 O(n)

  • 最佳情況

最佳情況下的時間複雜度是 O(n)。它與平均情況下的時間複雜度相同。

  • 最壞情況

最差的時間複雜度是 O(n)。它與最佳情況下的時間複雜度相同。

空間複雜度

該遍歷演算法的空間複雜度為 O(1),因為除了臨時指標外,不需要額外的空間。

作者: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Data Structure

相關文章 - Linked List