Leetcode 206 Reverse Linked List

文章目录

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

学习小窍门：对角线法则。

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

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 

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

思考一下为什么是错的？’

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

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

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