リンク リストのヘッド ノードへのポインタが与えられると、タスクはリンク リストを反転することです。ノード間のリンクを変更してリストを逆にする必要があります。
例 :
推奨される実践方法 リンクされたリストを逆にする 試してみましょう。入力 : 以下のリンク先リストの先頭
1->2->3->4->NULL
出力 : リンクされたリストを次のように変更する必要があります。
4->3->2->1->NULL入力 : 以下のリンク先リストの先頭
1->2->3->4->5->NULL
出力 : リンクされたリストを次のように変更する必要があります。
5->4->3->2->1->NULL入力 ： ヌル
出力 ： ヌル
入力 : 1->NULL
出力 : 1->NULL
反復法によるリンクリストを逆にする：
アイデアは 3 つのポインターを使用することです カレー 、 前へ、 そして 次 逆方向リンクを更新するためにノードを追跡します。
問題を解決するには、次の手順に従ってください。
- 3つのポインタを初期化する 前へ NULLとして、 カレー として 頭 、 そして 次 NULLとして。
- リンクされたリストを繰り返し処理します。ループ内で次の操作を実行します。
- 変更する前に、 次 の カレー 、保存します 次 ノード
- 次 = 現在 -> 次へ
- 今すぐ更新してください 次 のポインタ カレー に 前へ
- 現在 -> 次 = 前
- アップデート 前へ として カレー そして カレー として 次
- 前 = 現在
- 現在 = 次へ
- 変更する前に、 次 の カレー 、保存します 次 ノード
上記のアプローチの実装を以下に示します。
C++ // Iterative C++ program to reverse a linked list #include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; Node(int data) { this->データ = データ; 次 = NULL; } }; struct LinkedList { ノード * ヘッド; LinkedList() { ヘッド = NULL; } /* リンクリストを反転する関数 */ void reverse() { // 現在、前、次のポインタを初期化 Node* current = head; ノード *prev = NULL、*next = NULL; while (current != NULL) { // 次を保存します next = current->next; // 現在のノードのポインタを反転します current->next = prev; // ポインターを 1 つ前に移動します。 前 = 現在; 現在 = 次; } ヘッド = 前; } /* リンクリストを出力する関数 */ void print() { struct Node* temp = head; while (temp != NULL) { cout<< temp->データ<< ' '; temp = temp->次; void Push(int data) { Node* temp = new Node(data); temp->next = 頭; ヘッド = 温度; } }; /* ドライバー コード*/ int main() { /* 空のリストから開始します */ LinkedList ll; ll.push(20); ll.push(4); ll.push(15); ll.push(85); コート<< 'Given linked list
'; ll.print(); ll.reverse(); cout << '
Reversed linked list
'; ll.print(); return 0; }> C // Iterative C program to reverse a linked list #include #include /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list */ static void reverse(struct Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; struct Node* next = NULL; while (current != NULL) { // Store next next = current->次; // 現在のノードのポインタを反転します current->next = prev; // ポインターを 1 つ前に移動します。 前 = 現在; 現在 = 次; *head_ref = 前; } /* ノードをプッシュする関数 */ void Push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); 新しいノード->データ = 新しいデータ; new_node->next = (*head_ref); (*head_ref) = 新しいノード; } /* リンクリストを出力する関数 */ void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf('%d ', temp->data); temp = temp->next; } } /* ドライバー コード*/ int main() { /* 空のリストから開始 */ struct Node* head = NULL; プッシュ(&ヘッド, 20); プッシュ(&head, 4); プッシュ(&head, 15); プッシュ(&ヘッド, 85); printf('指定されたリンク リスト
'); printList(ヘッド); 逆方向(&ヘッド); printf('
逆リンク リスト
'); printList(ヘッド); getchar(); }>> ジャワ // Java program for reversing the linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to reverse the linked list */ 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; } // prints content of double linked list void printList(Node node) { while (node != null) { System.out.print(node.data + ' '); node = node.next; } } // Driver Code public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(85); list.head.next = new Node(15); list.head.next.next = new Node(4); list.head.next.next.next = new Node(20); System.out.println('Given linked list'); list.printList(head); head = list.reverse(head); System.out.println(''); System.out.println('Reversed linked list '); list.printList(head); } } // This code has been contributed by Mayank Jaiswal> パイソン # Python program to reverse a linked list # Time Complexity : O(n) # Space Complexity : O(1) # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to reverse the linked list def reverse(self): prev = None current = self.head while(current is not None): next = current.next current.next = prev prev = current current = next self.head = prev # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the LinkedList def printList(self): temp = self.head while(temp): print(temp.data, end=' ') temp = temp.next # Driver code llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print ('Given linked list') llist.printList() llist.reverse() print ('
Reversed linked list') llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> C# // C# program for reversing the linked list using System; class GFG { // Driver Code static void Main(string[] args) { LinkedList list = new LinkedList(); list.AddNode(new LinkedList.Node(85)); list.AddNode(new LinkedList.Node(15)); list.AddNode(new LinkedList.Node(4)); list.AddNode(new LinkedList.Node(20)); // List before reversal Console.WriteLine('Given linked list '); list.PrintList(); // Reverse the list list.ReverseList(); // List after reversal Console.WriteLine('Reversed linked list '); list.PrintList(); } } class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // function to add a new node at // the end of the list public void AddNode(Node node) { if (head == null) head = node; else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = node; } } // function to reverse the list public void ReverseList() { Node prev = null, current = head, next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } head = prev; } // function to print the list data public void PrintList() { Node current = head; while (current != null) { Console.Write(current.data + ' '); current = current.next; } Console.WriteLine(); } } // This code is contributed by Mayank Sharma> JavaScript >>
出力
Given linked list 85 15 4 20 Reversed linked list 20 4 15 85>
時間計算量: O(N)、サイズ N のリンクされたリストを横断します。
補助スペース: ○(1)
再帰を使用してリンクされたリストを逆順にします。
このアイデアは、再帰を使用してリンク リストの最後のノードに到達し、リンク リストを逆順に開始することです。
問題を解決するには、次の手順に従ってください。
- リストを 2 つの部分 (最初のノードとリンクされたリストの残り) に分割します。
- 残りのリンク リストに対して reverse を呼び出します。
- 残りのリンクリストを最初にリンクします。
- ヘッドポインタを NULL に修正
上記のアプローチの実装を以下に示します。
C++ // Recursive C++ program to reverse // a linked list #include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; Node(int data) { this->データ = データ; 次 = NULL; } }; struct LinkedList { ノード * ヘッド; LinkedList() { ヘッド = NULL; } Node* reverse(Node* head) /* リンクリストを出力する関数 */ void print() { struct Node* temp = head; while (temp != NULL) { cout<< temp->データ<< ' '; temp = temp->次; void Push(int data) { Node* temp = new Node(data); temp->next = 頭; ヘッド = 温度; } }; /* 上記の関数をテストするドライバー プログラム*/ int main() { /* 空のリストから開始します */ LinkedList ll; ll.push(20); ll.push(4); ll.push(15); ll.push(85); コート<< 'Given linked list
'; ll.print(); ll.head = ll.reverse(ll.head); cout << '
Reversed linked list
'; ll.print(); return 0; }> ジャワ // Recursive Java program to reverse // a linked list import java.io.*; class recursion { static Node head; // head of list static class Node { int data; Node next; Node(int d) { data = d; next = null; } } static Node reverse(Node head) /* Function to print linked list */ static void print() { Node temp = head; while (temp != null) { System.out.print(temp.data + ' '); temp = temp.next; } System.out.println(); } static void push(int data) { Node temp = new Node(data); temp.next = head; head = temp; } /* Driver program to test above function*/ public static void main(String args[]) { /* Start with the empty list */ push(20); push(4); push(15); push(85); System.out.println('Given linked list'); print(); head = reverse(head); System.out.println('Reversed linked list'); print(); } } // This code is contributed by Prakhar Agarwal> パイソン '''Python3 program to reverse linked list using recursive method''' # Linked List Node class Node: def __init__(self, data): self.data = data self.next = None # Create and Handle list operations class LinkedList: def __init__(self): self.head = None # Head of list # Method to reverse the list def reverse(self, head): # If head is empty or has reached the list end if head is None or head.next is None: return head # Reverse the rest list rest = self.reverse(head.next) # Put first element at the end head.next.next = head head.next = None # Fix the header pointer return rest # Returns the linked list in display format def __str__(self): linkedListStr = '' temp = self.head while temp: linkedListStr = (linkedListStr + str(temp.data) + ' ') temp = temp.next return linkedListStr # Pushes new data to the head of the list def push(self, data): temp = Node(data) temp.next = self.head self.head = temp # Driver code linkedList = LinkedList() linkedList.push(20) linkedList.push(4) linkedList.push(15) linkedList.push(85) print('Given linked list') print(linkedList) linkedList.head = linkedList.reverse(linkedList.head) print('Reversed linked list') print(linkedList) # This code is contributed by Debidutta Rath> C# // Recursive C# program to // reverse a linked list using System; class recursion { // Head of list static Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } static Node reverse(Node head) if (head == null // Function to print linked list static void print() { Node temp = head; while (temp != null) { Console.Write(temp.data + ' '); temp = temp.next; } Console.WriteLine(); } static void push(int data) { Node temp = new Node(data); temp.next = head; head = temp; } // Driver code public static void Main(String[] args) { // Start with the // empty list push(20); push(4); push(15); push(85); Console.WriteLine('Given linked list'); print(); head = reverse(head); Console.WriteLine('Reversed linked list'); print(); } } // This code is contributed by gauravrajput1> JavaScript >>
出力
Given linked list 85 15 4 20 Reversed linked list 20 4 15 85>
時間計算量: O(N)、すべてのノードを 1 回訪問します
補助スペース: O(N)、関数呼び出しスタック領域
末尾再帰法によるリンクリストを反転する：
アイデアは 3 つの指針を維持することです 前の 、 現在 そして 次 、すべてのノードに再帰的にアクセスし、これら 3 つのポインターを使用してリンクを作成します。
問題を解決するには、次の手順に従ってください。
- まず、現在の次のノードで次を更新します。つまり、 次 = 現在→次
- 次に、現在のノードから前のノードへの逆方向リンクを作成します。つまり、curr->next = prev
- 訪問したノードが最後のノードの場合は、現在のノードから前のノードへの逆方向リンクを作成し、ヘッドを更新するだけです。
上記のアプローチの実装を以下に示します。
C++ // A simple and tail recursive C++ program to reverse // a linked list #include using namespace std; struct Node { int data; struct Node* next; Node(int x) { data = x; next = NULL; } }; void reverseUtil(Node* curr, Node* prev, Node** head); // This function mainly calls reverseUtil() // with prev as NULL void reverse(Node** head) { if (!head) return; reverseUtil(*head, NULL, head); } // A simple and tail-recursive function to reverse // a linked list. prev is passed as NULL initially. void reverseUtil(Node* curr, Node* prev, Node** head) { /* If last node mark it head*/ if (!curr->next) { *head = curr; /* 前のノードの次を更新 */ curr->next = prev; 戻る; } /* 再帰呼び出し用に curr->next ノードを保存 */ Node* next = curr->next; /* そして次を更新します ..*/ curr->next = prev; reverseUtil(next、curr、head); } // リンクリストを出力するユーティリティ関数 void printlist(Node* head) { while (head != NULL) { cout<< head->データ<< ' '; head = head->次; }<< endl; } // Driver code int main() { Node* head1 = new Node(1); head1->次 = 新しいノード(2); head1->next->next = 新しいノード(3); head1->next->next->next = 新しいノード(4); head1->next->next->next->next = 新しいノード(5); head1->next->next->next->next->next = 新しいノード(6); head1->next->next->next->next->next->next = 新しいノード(7); head1->next->next->next->next->next->next->next = 新しいノード(8); コート<< 'Given linked list
'; printlist(head1); reverse(&head1); cout << 'Reversed linked list
'; printlist(head1); return 0; }> C // A simple and tail recursive C program to reverse a linked // list #include #include typedef struct Node { int data; struct Node* next; } Node; void reverseUtil(Node* curr, Node* prev, Node** head); // This function mainly calls reverseUtil() // with prev as NULL void reverse(Node** head) { if (!head) return; reverseUtil(*head, NULL, head); } // A simple and tail-recursive function to reverse // a linked list. prev is passed as NULL initially. void reverseUtil(Node* curr, Node* prev, Node** head) { /* If last node mark it head*/ if (!curr->next) { *head = curr; /* 前のノードの次を更新 */ curr->next = prev; 戻る; } /* 再帰呼び出し用に curr->next ノードを保存 */ Node* next = curr->next; /* そして次を更新します ..*/ curr->next = prev; reverseUtil(next、curr、head); } // 新しいノードを作成するユーティリティ関数 Node* newNode(int key) { Node* temp = (Node*)malloc(sizeof(Node)); 一時->データ = キー; 一時->次 = NULL; 戻り温度; } // リンクリストを出力するユーティリティ関数 void printlist(Node* head) { while (head != NULL) { printf('%d ', head->data); 頭 = 頭->次; printf('
'); } // ドライバー コード 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); printf('指定されたリンク リスト
'); printlist(head1); リバース(&head1); printf('逆リンクリスト
'); printlist(head1); 0を返します。 } // このコードは Aditya Kumar (adityakumar129) によって提供されました>> ジャワ // Java program for reversing the Linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // A simple and tail recursive function to reverse // a linked list. prev is passed as NULL initially. Node reverseUtil(Node curr, Node prev) { /*If head is initially null OR list is empty*/ if (head == null) return head; /* If last node mark it head*/ if (curr.next == null) { head = curr; /* Update next to prev node */ curr.next = prev; return head; } /* Save curr->再帰呼び出しの次のノード */ Node next1 = curr.next; /* そして次を更新します ..*/ curr.next = prev; reverseUtil(next1, curr); 頭を戻します。 } // 二重リンクリストの内容を出力します void printList(Node node) { while (node != null) { System.out.print(node.data + ' '); ノード = ノード.ネクスト; } } // ドライバー コード public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = 新しいノード(1); list.head.next = 新しいノード(2); list.head.next.next = 新しいノード(3); list.head.next.next.next = 新しいノード(4); list.head.next.next.next.next = 新しいノード(5); list.head.next.next.next.next.next = 新しいノード(6); list.head.next.next.next.next.next.next = 新しいノード(7); list.head.next.next.next.next.next.next.next = 新しいノード(8); System.out.println('指定されたリンク リスト '); list.printList(head); ノード res = list.reverseUtil(head, null); System.out.println('
逆リンク リスト '); list.printList(res); } } // このコードは Aditya Kumar (adityakumar129) によって提供されました>> パイソン # Simple and tail recursive Python program to # reverse a linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None def reverseUtil(self, curr, prev): # If last node mark it head if curr.next is None: self.head = curr # Update next to prev node curr.next = prev return # Save curr.next node for recursive call next = curr.next # And update next curr.next = prev self.reverseUtil(next, curr) # This function mainly calls reverseUtil() # with previous as None def reverse(self): if self.head is None: return self.reverseUtil(self.head, None) # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the linked LinkedList def printList(self): temp = self.head while(temp): print (temp.data, end=' ') temp = temp.next # Driver code llist = LinkedList() llist.push(8) llist.push(7) llist.push(6) llist.push(5) llist.push(4) llist.push(3) llist.push(2) llist.push(1) print ('Given linked list') llist.printList() llist.reverse() print ('
Reversed linked list') llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007)> C# // C# program for reversing the Linked list using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // A simple and tail-recursive function to reverse // a linked list. prev is passed as NULL initially. Node reverseUtil(Node curr, Node prev) { /* If last node mark it head*/ if (curr.next == null) { head = curr; /* Update next to prev node */ curr.next = prev; return head; } /* Save curr->再帰呼び出しの次のノード */ Node next1 = curr.next; /* そして次を更新します ..*/ curr.next = prev; reverseUtil(next1, curr); 頭を戻します。 } // 二重リンクリストの内容を出力します void printList(Node node) { while (node != null) { Console.Write(node.data + ' '); ノード = ノード.ネクスト; } } // ドライバー コード public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = 新しいノード(1); list.head.next = 新しいノード(2); list.head.next.next = 新しいノード(3); list.head.next.next.next = 新しいノード(4); list.head.next.next.next.next = 新しいノード(5); list.head.next.next.next.next.next = 新しいノード(6); list.head.next.next.next.next.next.next = 新しいノード(7); list.head.next.next.next.next.next.next.next = 新しいノード(8); Console.WriteLine('指定されたリンク リスト '); list.printList(list.head); ノード res = list.reverseUtil(list.head, null); Console.WriteLine('
逆リンク リスト '); list.printList(res); } } // このコードは Rajput-Ji によって提供されました>>'JavaScript>> 出力
Given linked list 1 2 3 4 5 6 7 8 Reversed linked list 8 7 6 5 4 3 2 1>
時間計算量: O(N)、サイズ N のリンク リストのすべてのノードを訪問します。
補助スペース: O(N)、関数呼び出しスタック領域
を使用してリンクされたリストを反転します このアイデアは、すべてのノードをスタックに保存し、逆方向にリンクされたリストを作成することです。
問題を解決するには、次の手順に従ってください。
- すべての値が入力されるまで、ノード (値とアドレス) をスタックに保存します。
- すべてのエントリが完了したら、Head ポインタを最後の位置 (つまり、最後の値) に更新します。
- ノード (値とアドレス) のポップを開始し、スタックが空になるまで同じ順序で格納します。
- スタック内の最後のノードの次のポインタを NULL で更新します。
上記のアプローチの実装を以下に示します。
C++ // C++ program for above approach #include #include using namespace std; // Create a class Node to enter values and address in the // list class Node { public: int data; Node* next; Node(int x) { data = x; next = NULL; } }; // Function to reverse the linked list void reverseLL(Node** head) { // Create a stack 's' of Node type stacks; ノード* 温度 = *ヘッド; while (temp->next != NULL) { // すべてのノードをスタックにプッシュします s.push(temp); temp = temp->next; *ヘッド = 温度; while (!s.empty()) { // スタックの先頭値をリストに格納 temp->next = s.top(); // スタックから値をポップします s.pop(); // リスト内の次のポインタを更新します temp = temp->next; temp->next = NULL; } // リスト内の要素を表示する関数 void printlist(Node* temp) { while (temp != NULL) { cout<< temp->データ<< ' '; temp = temp->次; } } // リンクされたリストの後ろに挿入するプログラム void insert_back(Node** head, int value) { // 後ろに挿入メソッドを使用して、 // リストに値を入力しました。(例: head->1->2->3->4->Null) ノード* 温度 = 新しいノード(値); 一時->次 = NULL; // *head が NULL に等しい場合 if (*head == NULL) { *head = temp; 戻る; } else { ノード* last_node = *head; while (last_node->next != NULL) last_node = last_node->next; last_node->next = 一時; 戻る; } } // ドライバーコード int main() { Node* head = NULL; insert_back(&head, 1); insert_back(&head, 2); insert_back(&head, 3); insert_back(&head, 4); コート<< 'Given linked list
'; printlist(head); reverseLL(&head); cout << '
Reversed linked list
'; printlist(head); return 0; } // This code is contributed by Aditya Kumar (adityakumar129)> ジャワ // Java program for above approach import java.util.*; class GFG { // Create a class Node to enter values and address in // the list static class Node { int data; Node next; Node(int x) { data = x; next = null; } }; static Node head = null; // Function to reverse the linked list static void reverseLL() { // Create a stack 's' of Node type Stacks = 新しいスタック(); ノード温度 = ヘッド; while (temp.next != null) { // すべてのノードをスタックにプッシュします s.add(temp); temp = temp.next; ヘッド = 温度; while (!s.isEmpty()) { // スタックの先頭値をリストに格納 temp.next = s.peek(); // スタックから値をポップします s.pop(); // リスト内の次のポインターを更新します temp = temp.next; temp.next = null; } // リスト内の要素を表示する関数 static void printlist(Node temp) { while (temp != null) { System.out.print(temp.data + ' '); temp = temp.next; } } // リンクされたリストの後ろに挿入するプログラム static void insert_back(int value) { // 後ろに挿入メソッドを使用して、 // リストに値を入力しました。(例: head.1.2.3.4.Null) ノードtemp = 新しいノード(値); temp.next = null; // *head が null に等しい場合 if (head == null) { head = temp; 戻る; } else { ノード last_node = head; while (last_node.next != null) last_node = last_node.next; last_node.next = 一時; 戻る; } } // ドライバーコード public static void main(String[] args) { insert_back(1); 挿入_バック(2); 挿入_バック(3); 挿入_バック(4); System.out.print('指定されたリンク リスト
'); プリントリスト(ヘッド); 逆LL(); System.out.print('
逆リンク リスト
'); プリントリスト(ヘッド); } } // このコードは Aditya Kumar (adityakumar129) によって提供されました>> パイソン # Python code for the above approach # Definition for singly-linked list. class ListNode: def __init__(self, val = 0, next=None): self.val = val self.next = next class Solution: # Program to reverse the linked list # using stack def reverseLLUsingStack(self, head): # Initialise the variables stack, temp = [], head while temp: stack.append(temp) temp = temp.next head = temp = stack.pop() # Until stack is not # empty while len(stack)>0: temp.next = stack.pop() temp = temp.next temp.next = なし return head # ドライバーコード if __name__ == '__main__': head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print('指定されたリンク リスト') temp = head while temp: print(temp.val, end=' ') temp = temp.next obj = Solution() print('
逆リンク リスト') head = obj.reverseLLUsingStack(head) while head: print(head.val, end=' ') head = head.next>> C# // C# program for above approach using System; using System.Collections.Generic; class GFG { // Create a class Node to enter // values and address in the list public class Node { public int data; public Node next; public Node(int x) { data = x; } }; static Node head = null; // Function to reverse the // linked list static void reverseLL() { // Create a stack 's' // of Node type Stacks = 新しいスタック(); ノード温度 = ヘッド; while (temp.next != null) { // すべてのノードを // スタックにプッシュします s.Push(temp); temp = temp.next; ヘッド = 温度; while (s.Count != 0) { // スタックの先頭の値をリストに格納 // temp.next = s.Peek(); // スタックから値をポップします s.Pop(); // リスト内の // 次のポインターを更新します。 temp = temp.next; temp.next = null; } // 表示する関数 // List 内の要素 static void printlist(Node temp) { while (temp != null) { Console.Write(temp.data + ' '); temp = temp.next; } } // リンクされたリストの後ろに挿入する関数 // static void insert_back(int val) { // リストに値を入力するために、 // 後ろに挿入メソッドを使用しました。(例: // head.1.2.3.4 .Null) ノード温度 = 新しいノード(val); temp.next = null; // *head が null に等しい場合 if (head == null) { head = temp; 戻る; } else { ノード last_node = head; while (last_node.next != null) { last_node = last_node.next; last_node.next = 一時; 戻る; } } // ドライバーコード public static void Main(String[] args) { insert_back(1); 挿入_バック(2); 挿入_バック(3); 挿入_バック(4); Console.Write('指定されたリンク リスト
'); プリントリスト(ヘッド); 逆LL(); Console.Write('
逆リンク リスト
'); プリントリスト(ヘッド); } } // このコードは gauravrajput1 によって提供されました>>'JavaScript>> 出力
Given linked list 1 2 3 4 Reversed linked list 4 3 2 1>
時間計算量: O(N)、サイズ N のリンク リストのすべてのノードを訪問します。
補助スペース: O(N)、スペースはスタックにノードを格納するために使用されます。