206. Reverse Linked List

  • 44.1%

https://leetcode.com/problems/reverse-linked-list

Reverse a singly linked list.

click to show more hints.

Hint:

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

Subscribe to see which companies asked this question


剑指offer 16

可以递归 可以迭代

方法一:

使用迭代的方法,保存三个指针。新建一个new_head,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* new_head = new ListNode(0);
new_head -> next = head;
ListNode* pre = new_head;
ListNode* cur = head;
while (cur && cur -> next) {
ListNode* temp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = temp;
}
return new_head -> next;
}
};

方法二:

迭代

我的代码实现:

Dec 7th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* new_head = nullptr;
while(head!=nullptr){
ListNode* nex = head->next;
head->next = new_head;
new_head = head;
head = nex;
}
return new_head;
}
};

保存两个指针,一个遍历的当前位置的指针,一个逆转的链表的头指针。在中间遍历的时候需要一个临时指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
while (head) {
ListNode* next = head -> next;
head -> next = pre;
pre = head;
head = next;
}
return pre;
}
};

我的代码实现

一个保存未来root的指针, 一个现在遍历到的节点的指针.遍历时,保存下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* pre=NULL;
while(head){
ListNode* nex = head->next;
head->next = pre;
pre = head;
head = nex;
}
return pre;
}
};

方法三:

递归

我的代码实现:

Dec 7th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;
ListNode* new_head = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return new_head;
}
};

使用递归的方法,其中head->next->next是将head->next就是head的下一位,是反转后的最后一位的指针指向head,然后,head的下一位设置为NULL,就完成了。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !(head -> next)) return head;
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return node;
}
};

我的代码实现:

递归版

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* pre = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return pre;
}
};

我的代码实现;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* node = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return node;
}
};

前两种是迭代,后一种是递归。


cpp


https://discuss.leetcode.com/topic/17916/8ms-c-iterative-and-recursive-solutions-with-explanations

8ms C++ Iterative and Recursive Solutions with Explanations

xWell, since the head pointer may also be modified, we create a new_head that points to it to facilitate the reverse process.

For the example list 1 -> 2 -> 3 -> 4 -> 5 in the problem statement, it will become 0 -> 1 -> 2 -> 3 -> 4 -> 5 (we init new_head -> val to be 0). Then we set a pointer pre to new_head and another cur to head. Then we keep inserting cur -> next after pre until cur becomes the last node. The code is follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* new_head = new ListNode(0);
new_head -> next = head;
ListNode* pre = new_head;
ListNode* cur = head;
while (cur && cur -> next) {
ListNode* temp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = temp;
}
return new_head -> next;
}
};

This link provides a more concise solution without using the new_head. The idea is to reverse one node at a time for the beginning of the list. The rewritten code is as follows.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
while (head) {
ListNode* next = head -> next;
head -> next = pre;
pre = head;
head = next;
}
return pre;
}
};

Well, both of the above solutions are iterative. The hint has also suggested us to use recursion. In fact, the above link has a nice recursive solution, whose rewritten code is as follows.

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !(head -> next)) return head;
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return node;
}
};

The basic idea of this recursive solution is to reverse all the following nodes after head. Then we need to set head to be the final node in the reversed list. We simply set its next node in the original list (head -> next) to point to it and sets its next to be NULL.


https://discuss.leetcode.com/topic/16162/c-solution-very-easy

C++ solution .. very easy..

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *temp = NULL , *nextNode = NULL;
while(head){
nextNode = head->next;
head->next = temp;
temp = head;
head = nextNode;
}
return temp;
}
};

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* new_head = new ListNode(0);
new_head->next = NULL;
while(head){
ListNode* next = head->next;
head->next = new_head->next;
new_head->next = head;
head = next;
}
return new_head->next;
}
};

python


https://discuss.leetcode.com/topic/14043/python-iterative-and-recursive-solution

Python Iterative and Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
prev = None
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
# @param {ListNode} head
# @return {ListNode}
def reverseList(self, head):
return self._reverse(head)

def _reverse(self, node, prev=None):
if not node:
return prev
n = node.next
node.next = prev
return self._reverse(n, node)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
while head:
next = head.next
head.next = pre
pre = head
head = next
return pre

谢谢你,可爱的朋友。