206. Reverse Linked List
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
题目说明：
已知链表的头指针head，将链表逆序而不使用额外的空间。
先给出链表的数据结构：
struct ListNode {
int val; // 数据域
ListNode *next; // 指针域
ListNode(int x): val(x), next(NULL) {} // 构造函数
};
如图：
image.png
解题思路：
方法1：就地逆置法
首先声明一个新链表 头结点的指针 ：ListNode *new_head = NULL；
步骤1：next = head->next
image.png
步骤2：head->next = new_head
image.png
步骤3：new_head = head
image.png
步骤4：head = next
image.png
方法2：头插法
首先声明一个新链表 头结点 ：ListNode new_head(0)；
步骤1：next = head->next
image.png
步骤2：head->next = new_head->next
image.png
步骤3：new_head->next = head
image.png
步骤4：new_head->next = head
image.png
自此，完成了一个节点的逆置过程；依次遍历链表中的所有节点，可以实现链表的逆序操作；其中要注意的是，头插法返回的应该是除去0节点的 head->next。
My Solution 1（C++ 就地逆置法完整实现）
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x): val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *new_head = NULL;
while(head) {
ListNode *next = head->next;
head->next = new_head;
new_head = head;
head = next;
}
return new_head;
}
};
int main() {
Solution S;
ListNode a = ListNode(1);
ListNode b = ListNode(2);
ListNode c = ListNode(3);
ListNode d = ListNode(4);
ListNode e = ListNode(5);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
ListNode *head = &a;
while(head) {
cout << head->val << "->";
head = head->next;
}
cout << endl;
head = S.reverseList(&a);
while(head) {
cout << head->val << "->";
head = head->next;
}
return 0;
}
Result
1->2->3->4->5->
5->4->3->2->1->
Process returned 0 (0x0) execution time : 0.031 s
Press any key to continue.
My Solution 2（python3 头插法实现）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
new_head = ListNode(0)
if head == None:
return head
while head:
next_p = head.next
head.next = new_head.next
new_head.next = head
head = next_p
return new_head.next
