首页 > 代码库 > leetcode - Reverse Linked List II

leetcode - 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->NULLm = 2 and n = 4,

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

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

题目要求O(1)的内存消耗和只遍历一遍链表

 

个人思路:

1、第m-1个结点记为start,第m个结点记为before,第m+1个结点记为current,从current开始向第n个结点前进,每次都把current结点插入到start结点的后面,直到current遍历完成

2、注意一下边界情况即可

代码:

#include <stddef.h>/*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)        {            return NULL;        }        //临时的头结点,仅仅是为了方便接下来的操作        ListNode *tmpHead = new ListNode(0);        tmpHead->next = head;        ListNode *start = tmpHead;        ListNode *before = NULL;        ListNode *current = head;        int pos = 0;                while (++pos != m)        {            start = current;            current = current->next;        }        before = current;        if (++pos <= n)        {            current = current->next;        }        while (pos <= n)        {            before->next = current->next;            current->next = start->next;            start->next = current;            current = before->next;            ++pos;        }        head = tmpHead->next;        delete tmpHead;        return head;    }};

 

leetcode - Reverse Linked List II