To reverse a linked list in Java, you can follow the following steps:
- Define a class for the linked list node. Each node will have a value and a reference to the next node.
<span class="hljs-keyword">class</span> <span class="hljs-title class_">ListNode</span> {
<span class="hljs-type">int</span> val;
ListNode next;
ListNode(<span class="hljs-type">int</span> val) {
<span class="hljs-built_in">this</span>.val = val;
<span class="hljs-built_in">this</span>.next = <span class="hljs-literal">null</span>;
}
}
- Create a method to reverse the linked list. This method will take the head of the list as input and return the new head of the reversed list.
<span class="hljs-keyword">public</span> ListNode <span class="hljs-title function_">reverseList</span><span class="hljs-params">(ListNode head)</span> {
<span class="hljs-type">ListNode</span> <span class="hljs-variable">prev</span> <span class="hljs-operator">=</span> <span class="hljs-literal">null</span>;
<span class="hljs-type">ListNode</span> <span class="hljs-variable">current</span> <span class="hljs-operator">=</span> head;
<span class="hljs-keyword">while</span> (current != <span class="hljs-literal">null</span>) {
<span class="hljs-type">ListNode</span> <span class="hljs-variable">next</span> <span class="hljs-operator">=</span> current.next;
current.next = prev;
prev = current;
current = next;
}
<span class="hljs-keyword">return</span> prev;
}
- Create a linked list and test the reverse method.
<span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">main</span><span class="hljs-params">(String[] args)</span> {
<span class="hljs-comment">// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5</span>
<span class="hljs-type">ListNode</span> <span class="hljs-variable">head</span> <span class="hljs-operator">=</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">ListNode</span>(<span class="hljs-number">1</span>);
<span class="hljs-type">ListNode</span> <span class="hljs-variable">second</span> <span class="hljs-operator">=</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">ListNode</span>(<span class="hljs-number">2</span>);
<span class="hljs-type">ListNode</span> <span class="hljs-variable">third</span> <span class="hljs-operator">=</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">ListNode</span>(<span class="hljs-number">3</span>);
<span class="hljs-type">ListNode</span> <span class="hljs-variable">fourth</span> <span class="hljs-operator">=</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">ListNode</span>(<span class="hljs-number">4</span>);
<span class="hljs-type">ListNode</span> <span class="hljs-variable">fifth</span> <span class="hljs-operator">=</span> <span class="hljs-keyword">new</span> <span class="hljs-title class_">ListNode</span>(<span class="hljs-number">5</span>);
head.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
<span class="hljs-comment">// Print the original list</span>
System.out.println(<span class="hljs-string">"Original List:"</span>);
printList(head);
<span class="hljs-comment">// Reverse the list</span>
<span class="hljs-type">ListNode</span> <span class="hljs-variable">reversedHead</span> <span class="hljs-operator">=</span> reverseList(head);
<span class="hljs-comment">// Print the reversed list</span>
System.out.println(<span class="hljs-string">"Reversed List:"</span>);
printList(reversedHead);
}
<span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">printList</span><span class="hljs-params">(ListNode head)</span> {
<span class="hljs-type">ListNode</span> <span class="hljs-variable">current</span> <span class="hljs-operator">=</span> head;
<span class="hljs-keyword">while</span> (current != <span class="hljs-literal">null</span>) {
System.out.print(current.val + <span class="hljs-string">" "</span>);
current = current.next;
}
System.out.println();
}
The above code will output:
<span class="hljs-variable">Original</span> <span class="hljs-built_in">List</span><span class="hljs-operator">:</span>
<span class="hljs-number">1</span> <span class="hljs-number">2</span> <span class="hljs-number">3</span> <span class="hljs-number">4</span> <span class="hljs-number">5</span>
<span class="hljs-variable">Reversed</span> <span class="hljs-built_in">List</span><span class="hljs-operator">:</span>
<span class="hljs-number">5</span> <span class="hljs-number">4</span> <span class="hljs-number">3</span> <span class="hljs-number">2</span> <span class="hljs-number">1</span>
The reverseList method uses three pointers: prev, current, and next. It iterates through the linked list, reversing the next pointers of each node to point to the previous node. At the end of the iteration, the last node becomes the new head of the reversed list, which is returned by the method.