Leetcode 206 Reverse Linked List
【摘要】
文章目录
1. 题意描述2. 思路解析一2.1 代码实现一，nex为局部变量2.1.1 C++代码2.1.2 Java代码2.1.3 Python代码
2.2 代码实现二，nex为全局变量2...
1. 题意描述
Reverse a singly linked list.反转链表是一个基础问题，但也是一个很重要的问题。
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
2. 思路解析一
通过prev、cur、nex三个指针，prev指向的是前一个节点，cur指向的是当前节点，nex指向的是当前节点的后一个节点，其中prev和cur是为了实现节点指向的反转。其中nex可作为局部变量，也可以作为全局变量。如果nex作为局部变量，它仅仅是是为了使cur不断后移(2020.3.4复习)，它的走向为nex = cur.next。nex为全局变量，并且它的走向为nex = nex.next。
2.1 代码实现一，nex为局部变量
2.1.1 C++代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* prev = NULL;
ListNode* cur = head;
while (cur) {
ListNode* nex = cur->next;
cur->next = prev;
prev = cur;
cur = nex;
}
return prev;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
学习小窍门：对角线法则。
2.1.2 Java代码
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode cur = head;
while (cur != null) {
ListNode nex = cur.next;
cur.next = prev;
prev = cur;
cur = nex;
}
return prev;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
2.1.3 Python代码
# 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
"""
if head == None or head.next == None:
return head
prev = None
cur = head
while cur:
nex = cur.next
cur.next = prev
prev = cur
cur = nex
return prev
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
2.2 代码实现二，nex为全局变量
错误代码为：
/**
* 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 == NULL || head->next == NULL) {
return head;
}
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* nex = head->next;
while (cur) {
cur->next = prev;
prev = cur;
cur = nex;
nex = nex->next;
}
return prev;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
思考一下为什么是错的？’
2.2.1 c++代码
/**
* 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 == NULL || head->next == NULL) {
return head;
}
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* nex = head->next;
while (cur) {
cur->next = prev;
prev = cur;
cur = nex;
if (nex == NULL) {
return prev;
}
nex = nex->next;
}
return prev;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
2.2.2 Java代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode cur = head;
ListNode nex = head.next;
while(cur != null) {
cur.next = prev;
prev = cur;
cur = nex;
if (nex == null) {
return prev;
}
nex = nex.next;
}
return prev;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
2.2.3 Python代码
# 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
"""
if head == None or head.next == None:
return head
prev = None
cur = head
nex = head.next
while cur:
cur.next = prev
prev = cur
cur = nex
if not nex:
return prev
nex = nex.next
return prev
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/herosunly/article/details/87521509
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）