[LeetCode系列]翻转链表问题II

给定一个链表和两个整数m, n, 翻转链表第m个节点到第n个节点(从1开始计数).

如, 给定链表: 1->2->3->4->5->NULL, 以及 m = 2, n = 4.

返回 1->4->3->2->5->NULL.

假定m和n满足约束条件: 1 ≤ m ≤ n ≤ 链表长度.

注意: 不能使用额外空间, 且只能遍历链表一次.

算法思路:

翻转的过程可以分解成3步:

把相邻的节点的指向关系倒置; 即 1->2<-3<-4 5->NULL

把第m-1个节点(1)指向第n个节点(4); 即 1->4->3->2 5->NULL

把第m个节点(2, 需要缓存)指向第n+1个节点(5). 即 1->4->3->2->5->NULL

/**

 * 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 || m == n)

            return head;

        ListNode *p = head;

        int count = ;

        while(count < m-)

        {

            p = p->next;

            count++;

        }

        ListNode *p1;

        if(m == )

            p1= p;

        else

        {

            p1 = p->next;

            count++;

        }

        ListNode *last = p1;

        ListNode *p2 = p1->next;

        ListNode *tmp = NULL;

        while(p2 && count < n)

        {

            tmp = p2->next;

            p2->next = p1;

            p1 = p2;

            p2 = tmp;

            count++;

        }

        last->next = tmp;

        if(m == )

            head = p1;

        else

            p->next = p1;

        return head;

    }

};

巴特西

[LeetCode系列]翻转链表问题II

最新文章

热门文章