题目:Reverse Linked List II
逆置链表m到n的之间的节点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == NULL || head->next == NULL ||m == n)return head; int count = 0; ListNode *p = head; ListNode *pre = NULL; while (count < m - 1){//找到m的节点的位置 pre = p; p = p->next; count++; } ListNode *start = p; while (count < n - 1){//找到n的节点的位置 p = p->next; count++; } reverseRecursion(start,p); if (pre == NULL){ return p; } pre->next = p; return head; } private: void reverseRecursion(ListNode *p,ListNode *end){//递归的方法逆置链表p ListNode *q; if (p->next == end){//倒数第二个节点 q = end->next; p->next->next = p; p->next = q; return; } reverseRecursion(p->next, end); q = p->next->next;//逆置当前节点 p->next->next = p; p->next = q; } };
能用递归就能用栈来实现,
用栈来逆置链表,做法如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == NULL || head->next == NULL ||m == n)return head; int count = 0; ListNode *p = head; ListNode *pre = NULL; while (count < m - 1){ pre = p; p = p->next; count++; } ListNode *start = p; while (count < n - 1){ p = p->next; count++; } if (pre == NULL){ return reverseNonRecursion(pre, start, p); }else{ reverseNonRecursion(pre,start,p); return head; } } private: ListNode *reverseNonRecursion(ListNode *pre, ListNode *p, ListNode *end){ stack<ListNode *>stackLN; ListNode *q = p; while (q != end){//入栈 stackLN.push(q); q = q->next; } end = end->next; if(pre == NULL)pre = q;//得到前一个节点 else pre->next = q; while (!stackLN.empty()){ p = stackLN.top(); stackLN.pop(); q->next = p;//逆置 q = q->next; } q->next = end; return pre; } };
直接用循环来逆置链表:
1->2->3->4->5;
(m,n)=(2,4);
p=2;pre=1;end=4;
q=5;
1)temp=p;
2)temp->next=q;//2->5
3)p=p->next;//p=3;
4)q=temp;//q=2;
循环1到4步
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if (head == NULL || head->next == NULL ||m == n)return head; int count = 0; ListNode *p = head; ListNode *pre = NULL; while (count < m - 1){ pre = p; p = p->next; count++; } ListNode *start = p; while (count < n - 1){ p = p->next; count++; } if (pre == NULL){ return reverseNonRecursion2(pre, start, p); }else{ reverseNonRecursion2(pre,start,p); return head; } } private: ListNode *reverseNonRecursion2(ListNode *pre, ListNode *p, ListNode *end){ ListNode *q = end->next; while (p != end){ ListNode *temp = p; p = p->next; temp->next = q; q = temp; } p->next = q; if (pre == NULL)return p; pre->next = p; return pre; } };