## Question

Reverse a linked list.

Example

Challenge
Reverse it in-place and in one-pass


## 題解1 - 非遞迴

temp = head->next;


### 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;
}

}
}


## 題解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:
"""
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

}
}


### 源碼分析

case1 和 case2 可以合在一起考慮，case3 返回的為新鏈表的頭節點，整個遞迴過程中保持不變。