61. 旋转链表

leetcode61:61. 旋转链表

题目描述

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

Example

输入：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

solution idea

按照旋转规则

逐次旋转，总共旋转k次。注意到链表旋转的周期是链表的长度(len)，所以只需旋转k % len次

• 倒数第二个元素变为最后一个元素指向NULL
• 最后一位元素更新成为链表首位，指向原链表首位

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !(head->next)) return head; // 链表长度是0或者一时直接返回原链表
        ListNode *q,*first=head,*p=head;
        int len=0;
        while(p) // 计算链表长度 len
        {
            p=p->next;
            len++;
        }
        k=k%len; //长度len 是链表旋转的一个周期
        p=head;
        while(k)
        {
             // 旋转一次
            while(p->next->next) p=p->next;  // p指向链表倒数第二个元素
            q=p->next; // q指向最后一个元素
            p->next=NULL;
            q->next=first;
            first=q;
            p=first; //头指针
            k--;
        }
        return first;
    }
};

将后k位移至链表首

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
/*
** 将后k位移至链表首
*/
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || !(head->next)) return head; // 链表长度是0或者一时直接返回原链表
        ListNode *end=head,*first=head,*p=head;
        int len=0;
        while(p) // 计算链表长度 len
        {
            p=p->next;
            len++;
        }
        k=k%len; //长度len 是链表旋转的一个周期
        if(k==0) return head;
        p=head;
        for(int i=0;i<len-k;i++)//first指向链表倒数k位
        {
            end=first; // end 指向倒数(k+1)位
            first=first->next; 
        }
        p=first;
        while(p->next) p=p->next;
        p->next=head;
        end->next=NULL;
        return first;
    }
};

参考文献

1. c++ prime 第5版