首页 > 代码库 > Reverse Linked List II

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:

Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition:

1 ≤ mn ≤ length of list.

思路:先找到输入链表的第m-1个节点(即prev指向的节点)和第m个节点(即curr指向的节点),每次取curr节点的后一个节点插到prev节点之后,执行该操作n-m次即可。

 1 class Solution { 2 public: 3     ListNode *reverseBetween(ListNode *head, int m, int n) { 4         if( head == 0 || head->next == 0 ) { return head; } 5         ListNode *prev = 0, *curr = head; 6         for( int i = 1; i < m; ++i ) { 7             prev = curr; curr = curr->next; 8         } 9         for( int i = m; i < n; ++i ) {10             ListNode *tmpNode = curr->next;11             curr->next = tmpNode->next;12             if( prev ) {13                 tmpNode->next = prev->next;14                 prev->next = tmpNode;15             } else {16                 tmpNode->next = head;17                 head = tmpNode;18             }19         }20         return head;21     }22 };