Question

Reverse a linked list.

Example

Challenge
Reverse it in-place and in one-pass


Solution1 - Non-recursively

It would be much easier to reverse an array than a linked list, since array supports random access with index, while singly linked list can ONLY be operated through its head node. So an approach without index is required.

Think about how '1->2->3' can become '3->2->1'. Starting from '1', we should turn '1->2' into '2->1', then '2->3' into '3->2', and so on. The key is how to swap two adjacent nodes.

temp = head -> next;


The above code maintains two pointer, prev and head, and keeps record of next node before swapping. More detailed analysis:

1. Keep record of next node
2. change head->next to prev
3. update prev with head, to keep moving forward
4. update head with the record in step 1, for the sake of next loop

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return {ListNode}
prev = None
while curr is not None:
temp = curr.next
curr.next = prev
prev = curr
curr = temp



C++

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *prev = NULL;
while (curr != NULL) {
ListNode *temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}

}
};


Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode prev = null;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}

}
}


Source Code Analysis

Already covered in the solution part. One more word, the assignment of prev is neat and skilled.

Complexity

Traversing the linked list leads to O(n) time complexity, and auxiliary space complexity is O(1).

Solution2 - Recursively

Three cases when the recursion ceases:

1. If given linked list is null, just return.
2. If given linked list has only one node, return that node.
3. If given linked list has at least two nodes, pick out the head node and regard the following nodes as a sub-linked-list, swap them, then recurse that sub-linked-list.

Be careful when swapping the head node (refer as nodeY) and head of the sub-linked-list (refer as nodeX ): First, swap nodeY and nodeX; Second, assign null to nodeY->next (or it would fall into infinite loop, and tail of result list won't point to null).

Python

"""
Definition of ListNode

class ListNode(object):

def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
Reverse it in-place.
"""
# case1: empty list
# case2: only one element list
# case3: reverse from the rest after head
# unlink list from the rest



C++

/**
* Definition of ListNode
*
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
*/
// case1: empty list
// case2: only one element list
// case3: reverse from the rest after head
// unlink list from the rest

}
};


Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
// case1: empty list
// case2: only one element list
// case3: reverse from the rest after head
// unlink list from the rest

}
}


Source Code Analysis

case1 and case2 can be combined.What case3 returns is head of reversed list, which means it is exact the same Node (tail of origin linked list) through the recursion.

Complexity

The depth of recursion: O(n). Time Complexity: O(N). Space Complexity (without considering the recursion stack): O(1).