要求
- 反转一个链表
- 不得改变节点的值
示例
- head->1->2->3->4->5->NULL
- NULL<-1<-2<-3<-4<-5<-head
思路
- 设置三个辅助指针
实现
- 50实现反转,51-52实现后移
1 #include <iostream>
2 using namespace std;
3
4 struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode(int x) : val(x), next(NULL) {}
8 };
9
10 ListNode* createLinkedList(int arr[], int n){
11 if( n == 0 )
12 return NULL;
13 ListNode* head = new ListNode(arr[0]);
14 ListNode* curNode = head;
15 for( int i = 1 ; i < n ; i ++ ){
16 curNode->next = new ListNode(arr[i]);
17 curNode = curNode->next;
18 }
19 return head;
20 }
21
22 void printLinkedList(ListNode* head){
23 ListNode* curNode = head;
24 while( curNode != NULL ){
25 cout << curNode->val << " -> ";
26 curNode = curNode->next;
27 }
28 cout<<"NULL"<<endl;
29 return;
30 }
31
32 void deleteLinkedList(ListNode* head){
33 ListNode* curNode = head;
34 while( curNode != NULL){
35 ListNode* delNode = curNode;
36 curNode = curNode->next;
37 delete delNode;
38 }
39 return;
40 }
41
42 class Solution {
43 public:
44 ListNode* reverseList(ListNode* head) {
45
46 ListNode* pre = NULL;
47 ListNode* cur = head;
48 while( cur != NULL){
49 ListNode* next = cur->next;
50 cur->next = pre;
51 pre = cur;
52 cur = next;
53 }
54 return pre;
55 }
56 };
57
58 int main(){
59 int arr[] = {1,2,3,4,5};
60 int n = sizeof(arr)/sizeof(int);
61
62 ListNode* head = createLinkedList(arr,n);
63 printLinkedList(head);
64
65 ListNode* head2 = Solution().reverseList(head);
66 printLinkedList(head2);
67
68 deleteLinkedList(head2);
69 return 0;
70 }
相关
- 92 Reverse Linked List II
- 83 Remove Duplicateds from Sorted List
- 86 Partition List
- 328 Odd Even Linked List
- 2 Add Two Numbers
- 445 Add Two Numbers II