Welcome to Subscribe On Youtube

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

  • 
    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;
            }
        }
    }
    
    ############
    
    /**
     * 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;
        }
    }
    
  • // 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:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
            pre, p = None, head
            while p:
                q = p.next
                p.next = pre
                pre = p
                p = q
            return pre
    
    
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            dummy = ListNode()
            curr = head
            while curr:
                next = curr.next
                curr.next = dummy.next
                dummy.next = curr
                curr = next
            return dummy.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
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func reverseList(head *ListNode) *ListNode {
    	dummy := &ListNode{}
    	curr := head
    	for curr != nil {
    		next := curr.Next
    		curr.Next = dummy.Next
    		dummy.Next = curr
    		curr = next
    	}
    	return dummy.Next
    }
    
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */
    
    function reverseList(head: ListNode | null): ListNode | null {
        if (head == null) {
            return head;
        }
        let pre = null;
        let cur = head;
        while (cur != null) {
            const next = cur.next;
            cur.next = pre;
            [pre, cur] = [cur, next];
        }
        return pre;
    }
    
    
  • /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function (head) {
        let dummy = new ListNode();
        let curr = head;
        while (curr) {
            let next = curr.next;
            curr.next = dummy.next;
            dummy.next = curr;
            curr = next;
        }
        return dummy.next;
    };
    
    
  • /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int val=0, ListNode next=null) {
     *         this.val = val;
     *         this.next = next;
     *     }
     * }
     */
    public class Solution {
        public ListNode ReverseList(ListNode head) {
            ListNode pre = null;
            for (ListNode p = head; p != null;)
            {
                ListNode t = p.next;
                p.next = pre;
                pre = p;
                p = t;
            }
            return pre;
        }
    }
    
  • // Definition for singly-linked list.
    // #[derive(PartialEq, Eq, Clone, Debug)]
    // pub struct ListNode {
    //   pub val: i32,
    //   pub next: Option<Box<ListNode>>
    // }
    //
    // impl ListNode {
    //   #[inline]
    //   fn new(val: i32) -> Self {
    //     ListNode {
    //       next: None,
    //       val
    //     }
    //   }
    // }
    impl Solution {
        pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            match head {
                None => None,
                Some(mut head) => {
                    let mut cur = head.next.take();
                    let mut pre = Some(head);
                    while let Some(mut node) = cur {
                        let next = node.next.take();
                        node.next = pre;
                        pre = Some(node);
                        cur = next;
                    }
                    pre
                }
            }
        }
    }
    
    

All Problems

All Solutions