Chào ace, bài này chúng ta sẽ tìm hiểu về Đảo ngược một linked list(Danh sách liên kết đơn) trong series tự học về cấu trúc dữ liệu và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.
Trong bài học này, chúng ta sẽ được cho trước một con trỏ trỏ đến node head của một linked list, nhiệm vụ cần làm là hãy đảo ngược lại linked list này. Bạn thấy đó, để có thể đảo ngược được linked list, chúng ta sẽ cần phải thay đổi các liên kết giữa các nodes.
Ví dụ:
Input: con trỏ Head của linked list sau đây
1->2->3->4->NULL
Output: Linked list cần phải được thay đổi thành,
4->3->2->1->NULL
Input: con trỏ Head của linked list sau đây
1->2->3->4->5->NULL
Output: Linked list cần phải được thay đổi thành,
5->4->3->2->1->NULL
Input: NULL
Output: NULL
Input: 1->NULL
Output: 1->NULL
Nội dung chính
1. Đảo ngược linked list bằng cách sử dụng vòng lặp
1. Khởi tạo ba con trỏ: prev bằng với NULL, curr bằng với head, và next bằng với NULL.
2. Lặp/duyệt qua toàn bộ linked list. Bên trong vòng lặp, làm những việc sau:
// Trước khi thay đổi con trỏ next của con trỏ current,
// hãy lưu lại node next
next = curr -> next
// Bây giờ, thay đổi con trỏ next của con trỏ current
// Đây là nơi mà sự đảo ngược diễn ra
curr -> next = prev
// Di chuyển con trỏ prev và con trỏ curr một bước về phía trước
prev = curr
curr = next
Sau đây sẽ là đoạn code cài đặt cái thuật toán đảo ngược một linked list sử dụng vòng lặp đã nêu ở trên, được viết bằng nhiều ngôn ngữ lập trình:
CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ C Java Python C#
C
// Iterative C program to reverse a linked list
#include <stdio.h>
#include <stdlib.h>
/* 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->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printf("Given linked list\n");
printList(head);
reverse(&head);
printf("\nReversed Linked list \n");
printList(head);
getchar();
}
C++
// Iterative C++ program to reverse
// a linked list
#include <iostream>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList()
{
head = NULL;
}
/* Function to reverse the linked list */
void reverse()
{
// Initialize current, previous and
// next pointers
Node* current = head;
Node *prev = NULL, *next = NULL;
while (current != NULL) {
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
}
/* 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;
}
};
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
LinkedList ll;
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.reverse();
cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
Java
// 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;
}
}
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);
}
} Python
# 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 linked LinkedList
def printList(self):
temp = self.head
while(temp):
print temp.data,
temp = temp.next
# Driver program to test above functions
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print "Given Linked List"
llist.printList()
llist.reverse()
print "\nReversed Linked List"
llist.printList() C#
// C# program for reversing the linked list
using System;
class GFG {
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();
}
} Kết quả in ra là:
Given linked list
85 15 4 20
Reversed Linked list
20 4 15 85 Độ phức tạp về thời gian: O (n)
Độ phức tạp không gian: O (1)
2. Đảo ngược linked list bằng cách sử dụng đệ quy
1. Chia linked list thành hai phần – node đầu tiên và phần còn lại của linked list
2. Gọi đến hàm reverse cho phần còn lại của linked list
3. Kết nối phần còn lại của linked list với node đầu tiên của linked list
4. Thay đổi con trỏ head
Sau đây sẽ là đoạn code cài đặt cái thuật toán đảo ngược một linked list sử dụng đệ quy đã nêu ở trên, được viết bằng nhiều ngôn ngữ lập trình:
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ Java Python3
C++
// Recursive C++ program to reverse
// a linked list
#include <iostream>
using namespace std;
/* Link list node */
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* head)
{
if (head == NULL || head->next == NULL)
return head;
/* reverse the rest list and put
the first element at the end */
Node* rest = reverse(head->next);
head->next->next = head;
/* tricky step -- see the diagram */
head->next = NULL;
/* fix the head pointer */
return rest;
}
/* 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;
}
};
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
LinkedList ll;
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);
cout << "Given linked list\n";
ll.print();
ll.head = ll.reverse(ll.head);
cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
Java
// Recursive Java program to reverse
// a linked list
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)
{
if (head == null || head.next == null)
return head;
/* reverse the rest list and put
the first element at the end */
Node rest = reverse(head.next);
head.next.next = head;
/* tricky step -- see the diagram */
head.next = null;
/* fix the head pointer */
return rest;
}
/* 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();
}
} Python3
"""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) Kết quả in ra là:
Given linked list
85 15 4 20
Reversed Linked list
20 4 15 85 Độ phức tạp về thời gian: O(n)
Độ phức tạp về không gian: O(1)
3. Đảo ngược linked list một cách đơn giản hơn bằng Tail Recursive – đệ quy đuôi
Dưới đây sẽ là phần code cài đặt cho cách làm này:
ĐOẠN CODE VÍ DỤ ĐƯỢC VIẾT BẰNG C++ Java Python3 C#
C++
// A simple and tail recursive C++ program to reverse
// a linked list
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
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;
/* Update next to prev node */
curr->next = prev;
return;
}
/* Save curr->next node for recursive call */
Node* next = curr->next;
/* and update next ..*/
curr->next = prev;
reverseUtil(next, curr, head);
}
// A utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print a linked list
void printlist(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// Driver program to test above functions
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 << "Given linked list\n";
printlist(head1);
reverse(&head1);
cout << "\nReversed linked list\n";
printlist(head1);
return 0;
}
Java
// 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 last node mark it head*/
if (curr.next == null) {
head = curr;
/* Update next to prev node */
curr.next = prev;
return head;
}
/* Save curr->next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
// prints content of double linked list
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("Original Linked list ");
list.printList(head);
Node res = list.reverseUtil(head, null);
System.out.println("");
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(res);
}
}
Python
# 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,
temp = temp.next
# Driver program
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 "\nReverse linked list"
llist.printList() 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->next node for recursive call */
Node next1 = curr.next;
/* and update next ..*/
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
// prints content of double linked list
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver code
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);
Console.WriteLine("Original Linked list ");
list.printList(list.head);
Node res = list.reverseUtil(list.head, null);
Console.WriteLine("");
Console.WriteLine("");
Console.WriteLine("Reversed linked list ");
list.printList(res);
}
} Kết quả in ra là:
Given linked list
1 2 3 4 5 6 7 8
Reversed linked list
8 7 6 5 4 3 2 1Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
 trong series tự học về cấu trúc dữ liệu và giải thuật){kind=link}