CodingInterview-反转链表

翻转链表的时候需要跟踪三个节点,last、current 和 next。基本原理是在每次翻转的时候,将 current 指向 last,但是这时候指向未翻转时候的下一个节点就会丢失,所以就使用 next 节点来跟踪未翻转的下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL) return NULL;
ListNode* last=NULL;
ListNode* current=pHead;
while(current!=NULL){
ListNode* next=current->next;
current->next=last;
last=current;
current=next;
}
return last;
}
};