Reverse Linked List
Build a singly linked list and reverse its links.
Work through the cases
3 examplesInput notation
List values separated by spaces; use an empty line for an empty list.Expected result
Reversed values separated by spaces, or empty for an empty list.Case 1
Input
2 5 8
Expected output
8 5 2
Case 2
Input
7
Expected output
7
Case 3
Input
(empty line)
Expected output
empty
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Storing nodes in an array and rebuilding backwards works, but only pointer rewrites are needed. Head insertion reverses the list in one pass: each node is inserted immediately after a dummy. When the scan ends, dummy.next is the new head and extra space is constant.
We create a dummy node dummy, then traverse the linked list and insert each node after the dummy node. After traversal, return dummy.next.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode();
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = dummy.next;
dummy.next = curr;
curr = next;
}
return dummy.next;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.