反向鏈接列表  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 我的旅行 Microsoft微軟 高通公司 Samsung SAP SAP實驗室 Snapdeal 百會
鍊錶

問題陳述  

問題“逆轉 鍊錶” 指出我們被賦予了鍊錶的首位。 我們必須通過更改鏈接之間的鏈接來反向鏈接列表,並返回反向鏈接列表的開頭。

  

10->20->30->40->NULL
NULL<-10<-20<-30<-40

解釋

通過更改鏈接之間的鏈接,我們已顛倒了鏈接列表。 因此,執行反向操作後的新鍊錶變為40-> 30-> 20-> 10-> NULL。

反向鏈接列表的方法  

迭代法

    1. 初始化當前指針為head。
    2. 將上一個和下一個指針初始化為NULL。
    3. 運行循環,直到當前指向NULL。
      1. 在下一個指針旁邊分配當前的下一個指針。
      2. 現在,將前一個指針分配給當前的下一個指針。
      3. 將當前分配給當前的前一個。
    4. 將頭分配給上一個。

反向鏈接列表

C ++代碼

#include <iostream>
using namespace std;
struct Node {
  int data;
  struct Node* next;
  Node(int data)
  {
    this->data = data;
    next = NULL;
  }
};
struct LinkedList {
  Node* head;
  LinkedList()
  {
    head = NULL;
  }
  void reverse()
  {
    Node* current = head;
    Node *prev = NULL, *next = NULL;
    while (current != NULL) {
      next = current->next;
      current->next = prev;
      prev = current;
      current = next;
    }
    head = prev;
  }
  void print()
  {
    struct Node* temp = head;
    while (temp != NULL) {
      cout << temp->data << " ";
      temp = temp->next;
    }
  }
  void push(int data)
  {
    Node* temp = new Node(data);
    temp->next = head;
    head = temp;
  }
};
int main()
{
  LinkedList ll;
  ll.push(40);
  ll.push(30);
  ll.push(20);
  ll.push(10);
  cout << "old linked list\n";
  ll.print();
  ll.reverse();
  cout << "\nnew Linked list \n";
  ll.print();
  return 0;
}
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Java代碼 

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverse(Node node) 
  { 
    Node prev = null; 
    Node current = node; 
    Node next = null; 
    while (current != null) { 
      next = current.next; 
      current.next = prev; 
      prev = current; 
      current = next; 
    } 
    node = prev; 
    return node; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  public static void main(String[] args) 
  { 
    LinkedList list = new LinkedList(); 
    list.head = new Node(10); 
    list.head.next = new Node(20); 
    list.head.next.next = new Node(30); 
    list.head.next.next.next = new Node(40); 
    System.out.println("old Linked list"); 
    list.printList(head); 
    head = list.reverse(head); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(head); 
  } 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

複雜度分析

時間複雜度

O(N) 因為我們只遍歷鍊錶一次。

也可以看看
編寫函數以獲取兩個鍊錶的交點
空間複雜度

O(1) 因為我們僅使用空間來存儲臨時變量。

遞歸方法 

  • 通過遍歷鏈接列表,將最後一個節點分配為頭節點。
  • 並將鏈接列表的最後返回的尾部鏈接到其上一個節點。 此步驟之後是遞歸地執行。

C ++代碼 

#include <iostream> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
  Node(int data) 
  { 
    this->data = data; 
    next = NULL; 
  } 
}; 
struct LinkedList { 
  Node* head; 
  LinkedList() 
  { 
    head = NULL; 
  } 
  Node* reverse(Node* node) 
  { 
    if (node == NULL) 
      return NULL; 
    if (node->next == NULL) { 
      head = node; 
      return node; 
    } 
    Node* node1 = reverse(node->next); 
    node1->next = node; 
    node->next = NULL; 
    return node; 
  } 
  /* Function to print linked list */
  void print() 
  { 
    struct Node* temp = head; 
    while (temp != NULL) { 
      cout << temp->data << " "; 
      temp = temp->next; 
    } 
  } 
  void push(int data) 
  { 
    Node* temp = new Node(data); 
    temp->next = head; 
    head = temp; 
  } 
}; 
int main() 
{ 
  LinkedList ll; 
  ll.push(40); 
  ll.push(30); 
  ll.push(20); 
  ll.push(10); 
  cout << "old linked list\n"; 
  ll.print(); 
  ll.reverse(ll.head); 
  cout << "\n new Linked list \n"; 
  ll.print(); 
  return 0; 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

Java代碼來反向鏈接列表

import java.io.BufferedWriter; 
import java.io.IOException; 
import java.io.OutputStreamWriter; 
import java.util.Scanner; 
class ReverseLinkedListRecursive { 
    static class Node { 
    public int data; 
    public Node next; 
    public Node(int nodeData) { 
      this.data = nodeData; 
      this.next = null; 
    } 
  } 
  static class LinkedList { 
    public Node head; 
    public LinkedList() { 
      this.head = null; 
    } 
    public void insertNode(int nodeData) { 
      Node node = new Node(nodeData); 
      if (this.head != null) { 
        node.next = head; 
      } 
      this.head = node; 
    } 
  } 
  public static void printSinglyLinkedList(Node node, 
            String sep) throws IOException { 
    while (node != null) { 
      System.out.print(String.valueOf(node.data) + sep); 
      node = node.next; 
    } 
  } 
  static Node reverse(Node head) { 
    if(head == null) { 
      return head; 
    } 
    if(head.next == null) { 
      return head; 
    } 
    Node newHeadNode = reverse(head.next); 
    head.next.next = head; 
    head.next = null; 
    return newHeadNode; 
  } 
  private static final Scanner scanner = new Scanner(System.in); 
  public static void main(String[] args) throws IOException { 
      LinkedList llist = new LinkedList(); 
    
      llist.insertNode(40); 
      llist.insertNode(30); 
      llist.insertNode(20); 
      llist.insertNode(10); 
      
      System.out.println("old linked list:"); 
      printSinglyLinkedList(llist.head, " "); 
      
      System.out.println(); 
      System.out.println("new Linked list:"); 
      Node llist1 = reverse(llist.head); 
      printSinglyLinkedList(llist1, " "); 
    scanner.close(); 
  } 
} 
old linked list: 
10 20 30 40

new Linked list: 
40 30 20 10

複雜度分析

時間複雜度

O(N) 因為我們只遍歷鍊錶一次。

也可以看看
給定二叉樹中的垂直和
空間複雜度

O(N) 因為我們正在使用空間在編譯器堆棧上存儲臨時變量。 這些臨時變量取決於鏈接列表中節點的數量。

尾遞歸方法 

這種方法是一種遞歸,也稱為尾遞歸。 在尾部遞歸中,我們無需返回到已啟動其調用的函數。 我們將先前調用的結果值作為參數傳遞給新函數調用。 這在編譯器級別也很有用,因為我們不需要維護系統堆棧來存儲先前調用的值。 這也有助於防止堆棧溢出。

C ++代碼 

#include <bits/stdc++.h> 
using namespace std; 
struct Node { 
  int data; 
  struct Node* next; 
}; 
void reverseUtil(Node* curr, Node* prev, Node** head); 
void reverse(Node** head) 
{ 
  if (!head) 
    return; 
  reverseUtil(*head, NULL, head); 
} 
void reverseUtil(Node* curr, Node* prev, Node** head) 
{ 
  if (!curr->next) { 
    *head = curr; 
    curr->next = prev; 
    return; 
  } 
  Node* next = curr->next; 
  curr->next = prev; 
  reverseUtil(next, curr, head); 
} 
Node* newNode(int key) 
{ 
  Node* temp = new Node; 
  temp->data = key; 
  temp->next = NULL; 
  return temp; 
} 
void printlist(Node* head) 
{ 
  while (head != NULL) { 
    cout << head->data << " "; 
    head = head->next; 
  } 
  cout << endl; 
} 
int main() 
{ 
  Node* head1 = newNode(1); 
  head1->next = newNode(2); 
  head1->next->next = newNode(3); 
  head1->next->next->next = newNode(4); 
  head1->next->next->next->next = newNode(5); 
  head1->next->next->next->next->next = newNode(6); 
  head1->next->next->next->next->next->next = newNode(7); 
  head1->next->next->next->next->next->next->next = newNode(8); 
  cout << "old linked list\n"; 
  printlist(head1); 
  reverse(&head1); 
  cout << "\nnew linked list\n"; 
  printlist(head1); 
  return 0; 
} 
old linked list
1 2 3 4 5 6 7 8

new linked list
8 7 6 5 4 3 2 1

Java代碼 

class LinkedList { 
  static Node head; 
  static class Node { 
    int data; 
    Node next; 
    Node(int d) 
    { 
      data = d; 
      next = null; 
    } 
  } 
  Node reverseUtil(Node curr, Node prev) 
  { 
    if (curr.next == null) { 
      head = curr; 
      curr.next = prev; 
      return head; 
    } 
    Node next1 = curr.next; 
    curr.next = prev; 
    reverseUtil(next1, curr); 
    return head; 
  } 
  void printList(Node node) 
  { 
    while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
    } 
  } 
  public static void main(String[] args) 
  { 
    LinkedList list = new LinkedList(); 
    list.head = new Node(1); 
    list.head.next = new Node(2); 
    list.head.next.next = new Node(3); 
    list.head.next.next.next = new Node(4); 
    list.head.next.next.next.next = new Node(5); 
    list.head.next.next.next.next.next = new Node(6); 
    list.head.next.next.next.next.next.next = new Node(7); 
    list.head.next.next.next.next.next.next.next = new Node(8); 
    System.out.println("Old Linked list "); 
    list.printList(head); 
    Node res = list.reverseUtil(head, null); 
    System.out.println(""); 
    System.out.println(""); 
    System.out.println("new linked list "); 
    list.printList(res); 
  } 
}
old linked list 
1 2 3 4 5 6 7 8
new linked list 
8 7 6 5 4 3 2 1

複雜度分析

時間複雜度

O(N) 因為我們只遍歷鍊錶一次。

也可以看看
兩個鍊錶的並集和相交
空間複雜度

O(N) 因為我們使用空間僅在編譯器堆棧上存儲臨時變量。 這些臨時變量取決於鏈接列表中節點的數量。

參考