# ￼Reverse Linked List

## Question

Reverse a linked list.

Example
For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge
Reverse it in-place and in one-pass


## 题解1 - 非递归

temp = head->next;
head->next = prev;
prev = head;
head = temp;


1. 保存head下一节点
2. 将head所指向的下一节点改为prev
3. 将prev替换为head，波浪式前进
4. 将第一步保存的下一节点替换为head，用于下一次循环

### Python

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

class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
prev = None
curr = head
while curr is not None:
temp = curr.next
curr.next = prev
prev = curr
curr = temp
# fix head
head = prev

return head


### C++

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode* head) {
ListNode *prev = NULL;
ListNode *curr = head;
while (curr != NULL) {
ListNode *temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
// fix head
head = prev;

return head;
}
};


### Java

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// fix head
head = prev;

return head;
}
}


## 题解2 - 递归

1. 原链表为空，直接返回空链表即可。
2. 原链表仅有一个元素，返回该元素。
3. 原链表有两个以上元素，由于是单链表，故翻转需要自尾部向首部逆推。

### Python

"""
Definition of ListNode

class ListNode(object):

def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# case1: empty list
if head is None:
return head
# case2: only one element list
if head.next is None:
return head
# case3: reverse from the rest after head
newHead = self.reverse(head.next)
# reverse between head and head->next
head.next.next = head
# unlink list from the rest
head.next = None

return newHead


### C++

/**
* Definition of ListNode
*
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The new head of reversed linked list.
*/
ListNode *reverse(ListNode *head) {
// case1: empty list
if (head == NULL) return head;
// case2: only one element list
if (head->next == NULL) return head;
// case3: reverse from the rest after head
ListNode *newHead = reverse(head->next);
// reverse between head and head->next
head->next->next = head;
// unlink list from the rest
head->next = NULL;

return newHead;
}
};


### Java

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverse(ListNode head) {
// case1: empty list
if (head == null) return head;
// case2: only one element list
if (head.next == null) return head;
// case3: reverse from the rest after head
ListNode newHead = reverse(head.next);
// reverse between head and head->next
head.next.next = head;
// unlink list from the rest
head.next = null;

return newHead;
}
}


### 源码分析

case1 和 case2 可以合在一起考虑，case3 返回的为新链表的头节点，整个递归过程中保持不变。

powered by