leetcode 92. 反转链表 II

 1 #include"iostream"
 2 using namespace std;
 3 struct ListNode {
 4     int val;
 5     ListNode* next;
 6     ListNode(int x) : val(x), next(NULL) {}
 7 };
 8 
 9 class Solution {
10 public:
11     ListNode* reverseBetween(ListNode* head, int m, int n) {
12         ListNode* result = head;  //设置个用于输出结果的指针，=head
13         ListNode* pre_head=NULL, * modify_list_tail=NULL, * new_head=NULL;//需要三个辅助的指针，一定要先初始化
14         int len = n - m + 1;//求出要操作的节点个数，也就是在设置逆序的次数
15         while (head != NULL && --m) {   //找到开始逆序的位置
16             pre_head = head;            //pre_head是要中间逆序链表头的前一个节点
17             head = head->next;       
18         }
19         modify_list_tail = head;       //该头结点是逆序完成后的尾结点
20         new_head = NULL;
21         while(head&&len) {             //逆序过程
22             ListNode *next = head->next;
23             head->next = new_head;
24             new_head = head;
25             head = next;
26             len--;
27         }
28         modify_list_tail->next = head;  //原头节点变尾结点了，要将其next指向当前head
29         //判断是不是从第一个节点开始的逆序
30         if (pre_head) {                 //不是
31             pre_head->next = new_head;
32         }
33         else                           //是
34         {
35             result = new_head;
36         }
37         return result;
38     }
39 };
40 
41 
42 int main()
43 {
44     int m, n;
45     m = 2;
46     n = 4;
47     ListNode a(1);
48     ListNode b(2);
49     ListNode c(3);
50     ListNode d(4);
51     ListNode e(5);
52     a.next = &b;
53     b.next = &c;
54     c.next = &d;
55     d.next = &e;
56     e.next = NULL;
57     Solution s1;
58     ListNode* head = &a;//遍历需要个辅助的头指针啊
59     printf("before reverse:\n");
60     while (head) {
61         printf("%d\n", head->val);
62         head = head->next;
63     }
64     printf("after reverse:\n");
65     head = s1.reverseBetween(&a,m,n);
66     while (head) {
67         printf("%d\n", head->val);
68         head = head->next;
69     }
70     system("pause");
71     return 0;
72 }