Question
Formatted question description: https://leetcode.ca/all/206.html
206. Reverse Linked List
Level
Easy
Description
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution
The recursive solution is to do the reverse operation for head.next
, and set head.next.next = head
and head.next = null
.
The iterative solution uses two pointers, prev
and curr
. Initially, prev
is null
and curr
points to head
. Each step, let nextTemp
be the next node of curr
before reversing curr
. Set curr.next = prev
. After that, set both prev
and curr
to the next step (that is, prev = curr
and curr = nextTemp
). The loop ends when all nodes in the original list are reversed.
Code
Java
public class Reverse_Linked_List {
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/*
1,2,3,4,5
2,1 prev=2 - 3,4,5 current=3
3,2,1 prev=3 - 4,5 current=4
...
*/
// https://leetcode.com/problems/reverse-linked-list/solution/
class Solution_oj_iterative {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}
class Solution_oj_recursively {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
}
class Solution_recursively {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(0);
// dummy.next = head;
ListNode current = head;
reverse(dummy, current);
return dummy.next;
}
private void reverse(ListNode dummy, ListNode current) {
if (current == null) {
return;
}
ListNode newHead = current.next;
ListNode oldDummyNext = dummy.next;
dummy.next = current;
current.next = oldDummyNext;
current = newHead;
this.reverse(dummy, current);
}
}
class Solution_iteratively {
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(0);
// dummy.next = head;
ListNode current = head;
while (current != null) {
ListNode newHead = current.next;
ListNode oldDummyNext = dummy.next;
dummy.next = current;
current.next = oldDummyNext;
current = newHead;
}
return dummy.next;
}
}
}