206. Reverse Linked List

206. Reverse Linked List

题目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

思路

新建一个表头,通过循环依次反转链表指针方向就好。 1->2->3->4->5->NULL 变成 NULL<-1<-2<-3<-4<-5

代码

1
2
3
4
5
6
7
8
9
10
ListNode* reverseList(ListNode* head) {
ListNode* result = NULL;
while(head) {
ListNode* cur = head->next;
head->next = result;
result = head;
head = cur;
}
return result;
}

之前一直写错成这样是不对的,cur指向head的地址,改变了cur->next的值相当于改变了head->next的值,这样写结果只会返回链表第一个值:

1
2
3
4
5
6
7
8
9
10
11
//C++
ListNode* reverseList(ListNode* head) {
ListNode* result = NULL;
while(head) {
ListNode* cur = head;
cur->next = result;
result = cur;
head = head->next;
}
return result;
}

https://leetcode.com/problems/reverse-linked-list/discuss/58130/8ms-C++-Iterative-and-Recursive-Solutions-with-Explanations

打赏