LeetCode 61. 旋转链表

题目：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解题思路
首先看到若向右移动大于链表长度时，相当于向右移动 k % length.
方法一：
我发现想有移动多少距离，相当于最后K个节点逆转，以及前面的所有节点逆转，再将整个链表逆转即可。
但是这样需要确定后面k个节点的位置。
1.将整个链表逆转
不如先将链表逆转，在逆转前k个节点，在逆转后length - k个节点。

代码实现（c++）

ListNode* rev(ListNode* head)                              //链表逆转
    {
        if(!head || !head->next)
            return head;
        ListNode* newhead = rev(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
    ListNode* rotateRight(ListNode* head, int k) {
        int length = 0;
        if(!head || !head->next)
            return head;
        ListNode*  p = head;
        while(p)
        {
            ++length;
            p = p->next;
        }
        int k1 = k % length;
        if(k1 == 0)
            return head;
        ListNode* head1 = rev(head);
        ListNode* p1 = head1;
        while(k1 > 1)
        {
            --k1;
            p1 = p1->next;
        }
        ListNode* temp = p1->next;
        p1->next = nullptr;
        p1 = temp;
        ListNode* head2 = rev(p1);               //逆转后length - k1个节点
        ListNode* head3 = rev(head1);        //逆转前k个节点
        head1->next = head2;
        return head3;
        
    }

时间：16ms

方法二(双指针法）：
1.找到倒数第k+1个节点，以及最后一个节点的位置。
2.将最后一个节点指向head；
3.返会倒数第k个节点，并将倒数k+1个节点的next节点设置尾nullptr

代码实现(C++)

ListNode* rotateRight(ListNode* head, int k) {
        int length = 0;
        if(!head || !head->next)
            return head;
        ListNode*  p = head;
        while(p)
        {
            ++length;
            p = p->next;
        }
        int k1 = k % length;
        if(k1 == 0)
            return head;
        ListNode *first = head, *second = head;
        while(k1 )
        {
            --k1;
            first = first->next;
        }
        while(first->next)                                 //找到倒数第k1+1个节点和最后一个节点
        {
            first = first->next;
            second = second->next;
        }
        first->next = head;     
        ListNode* head1 = second->next;
        second->next = nullptr;                                 //断开链表
        return head1;
    
    }

时间：8ms

LeetCode 61. 旋转链表

相关推荐