This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Reverse a singly linked list.

A linked list can be reversed either iteratively or recursively. Could you implement both?

b'

\n\n## Solution

\n

\n#### Approach #1 (Iterative) [Accepted]

\n\n

\n#### Approach #2 (Recursive) [Accepted]

\n\n

'
\n

Assume that we have linked list `1 \xe2\x86\x92 2 \xe2\x86\x92 3 \xe2\x86\x92 \xc3\x98`

, we would like to change it to `\xc3\x98 \xe2\x86\x90 1 \xe2\x86\x90 2 \xe2\x86\x90 3`

.

While you are traversing the list, change the current node\'s next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

\npublic ListNode reverseList(ListNode head) {\n ListNode prev = null;\n ListNode curr = head;\n while (curr != null) {\n ListNode nextTemp = curr.next;\n curr.next = prev;\n prev = curr;\n curr = nextTemp;\n }\n return prev;\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : .\nAssume that is the list\'s length, the time complexity is .

\n \n - \n
Space complexity : .

\n \n

\n

The recursive version is slightly trickier and the key is to work backwards. Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let\'s assume the list is: n_{1} \xe2\x86\x92 \xe2\x80\xa6 \xe2\x86\x92 n_{k-1} \xe2\x86\x92 n_{k} \xe2\x86\x92 n_{k+1} \xe2\x86\x92 \xe2\x80\xa6 \xe2\x86\x92 n_{m} \xe2\x86\x92 \xc3\x98

Assume from node n_{k+1} to n_{m} had been reversed and you are at node n_{k}.

n_{1} \xe2\x86\x92 \xe2\x80\xa6 \xe2\x86\x92 n_{k-1} \xe2\x86\x92 **n _{k}** \xe2\x86\x92 n

We want n_{k+1}\xe2\x80\x99s next node to point to n_{k}.

So,

\nn_{k}.next.next = n_{k};

Be very careful that n_{1}\'s next must point to \xc3\x98. If you forget about this, your linked list has a cycle in it. This bug could be caught if you test your code with a linked list of size 2.

public ListNode reverseList(ListNode head) {\n if (head == null || head.next == null) return head;\n ListNode p = reverseList(head.next);\n head.next.next = head;\n head.next = null;\n return p;\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : .\nAssume that is the list\'s length, the time complexity is .

\n \n - \n
Space complexity : .\nThe extra space comes from implicit stack space due to recursion. The recursion could go up to levels deep.

\n \n