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;
}
}
}