A singly linked list is a data structure that allows for sequential access. It stores data elements of a linear list in a group of storage units with arbitrary addresses. The data in the linked list is represented by nodes, each consisting of an element and a pointer. The element is the 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 contents are 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 stores the data of the corresponding node, and the other stores the address of the next node, which can be called the successor pointer (next). The diagram below shows a representation of 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 that 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.
During the reversal, the next pointer of node A points to null, then the next pointer of node B points to node A. Finally, the traversal is completed and the singly linked list is reversed. The diagram below shows the traversal and reversal of a singly linked list:
The specific code is as follows:
/**
* Reverse a linked list (traversal)
*
* @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. Repeat this process for each node.
* During the reversal, we need to be careful about breaking the links in the list to avoid losing any nodes.
*
* 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 linked list with multiple nodes can be further divided into smaller linked lists. For example, a linked list with one node is just the node itself, and a linked list with two nodes, A->B->null, can be reversed by reversing the pointers of adjacent nodes. This means that the next pointer of node B should point to node A, and the next pointer of node A should be set to null. The code representation is as follows:
// Reverse the linked list A->B->null
B.next = A;
A.next = null;
The diagram below shows the recursive reversal of 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.
*
* When reversing a linked list, 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 explanation introduces singly linked lists and two ways to reverse them. If there are any errors, please feel free to point them out.