A singly linked list is a data structure that allows for chained access, using a group of storage units with arbitrary addresses to store data elements in a linear table. The data in the linked list is represented by nodes, each consisting of an element and a pointer. The element is a storage unit for storing data, and the pointer is the address data that connects each node. This article will introduce what a singly linked list is and how to reverse it. The main content is as follows:
- What is a singly linked list
- Traversing and reversing a singly linked list
- Recursively reversing a singly linked list
What is a singly linked list#
For each node in a singly linked list, there are two storage areas: one for storing the data of the corresponding node, and the other for storing the address of the next node. This can be called the successor pointer (next). The diagram below shows a singly linked list:
-
Head node: The first node of the linked list, used to record the base address of the list.
-
Tail node: The last node of the linked list, with its successor pointer (next) pointing to a null address.
Traversing and reversing a singly linked list#
Remember, reversing a linked list actually means reversing the pointers in the list. Assuming the singly linked list is A->B->C->D, the reversed list would be D->C->B->A. Reversing a singly linked list by traversing means reversing each node one by one.
When reversing, the next pointer of node A points to null, then the next pointer of node B points to node A, and so on, until the traversal is complete and the singly linked list is reversed. The diagram below shows the process of traversing and reversing a singly linked list:
The specific code is as follows:
/**
* Reverse a linked list (traversing)
*
* @param head
* @return
*/
public Node<T> reverse(Node<T> head) {
/**
* Idea: To reverse a linked list A->B->C->D, we need to make the head node, which is node A, point to null, and then make the next pointer of node B point to node A, and so on.
* During the reversal process, we need to be careful not to lose the disconnected parts of the list.
*
* Reversing a linked list actually means reversing the pointers in the list.
*/
Node<T> tempNode = null;
while (head != null) {
// Record the disconnected part of the list due to reversal
Node<T> nextNode = head.next;
// Reverse the list
head.next = tempNode;
// Move the tempNode pointer
tempNode = head;
// Move the head pointer
head = nextNode;
}
return tempNode;
}
Recursively reversing a singly linked list#
The second way to reverse a singly linked list is through recursion. The core idea is to break down a big problem into smaller problems. In other words, a singly linked list with multiple nodes can be further divided into smaller singly linked lists. For example, a singly linked list with one node is just the node itself, and a singly linked list with two nodes A->B->null can be reversed by reversing the pointers of adjacent nodes, which means making the next pointer of node B point to node A. At this point, the next pointer of node A still points to node B, so we need to make the next pointer of node A point to null. The code representation is as follows:
// Reverse the list A->B->null
B.next = A;
A.next = null;
The diagram below shows the process of recursively reversing a singly linked list:
The specific code is as follows:
/**
* Reverse a linked list (recursion)
*
* @param head
* @return
*/
public Node<T> reverse(Node<T> head) {
/**
* Idea: Use recursion to solve the problem.
*
* Always remember to reverse the pointers of two adjacent nodes.
*/
if (head == null || head.next == null) {
return head;
}
// newNode is the final head node after reversal
Node<T> newNode = reverse1(head.next);
head.next.next = head;
head.next = null;
return newNode;
}
The above content introduces singly linked lists and two ways to reverse them. If there are any errors, please feel free to point them out.