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; // initial node, oldDummyNext is null, which is what we want, and which is why "// dummy.next = head;" is commented out above current = newHead; } return dummy.next; } } }
-
// OJ: https://leetcode.com/problems/reverse-linked-list/ // Time: O(N) // Space: O(1) class Solution { public: ListNode* reverseList(ListNode* head) { ListNode h; while (head) { auto p = head; head = head->next; p->next = h.next; h.next = p; } return h.next; } };
-
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseList(self, root): if not root or not root.next: return root ret = self.reverseList(root.next) root.next.next = root root.next = None return ret def _reverseList(self, head): pre = None cur = head while cur: tmp = cur.next cur.next = pre pre = cur cur = tmp return pre # iteratively as queue head inserting def __reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ dHead = dummy = ListNode(-1) p = head while p: tmp = dummy.next dummy.next = p p = p.next dummy.next.next = tmp return dHead.next # easily leads to a circle. Remove current node's next after recursive call. def ___reverseList(self, head): self.newHead = None def rec(head): if not head: return head p = rec(head.next) head.next = None if p: p.next = head else: self.newHead = head return head rec(head) return self.newHead