首页 > 代码库 > [LeetCode 题解]: Rotate List

[LeetCode 题解]: Rotate List

2024-07-15 04:51:01   219人阅读

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

题意：

翻转链表。

思路：

首先需要读懂题意。题目的描述有问题，应该是将链表的最后k个元素移动到链表的头部。

这道题的本质就是寻找链表的倒数第k个元素。在该点将链表分成两个部分，然后调换顺序即可。

陷阱：

k的长度没有说明，可能k比链表的长度还要大。 设链表的长度为Len，那么移动的节点个数应该为 K%Len.

　　    

class Solution {public:    int getListLength(ListNode *head){        int len=0;        ListNode *tmp=head;        while(tmp){            len++;            tmp = tmp->next;        }        return len;    }    ListNode *rotateRight(ListNode *head, int x) {        if(head==NULL) return head;  // empty list        int len = getListLength(head);        x = x%len; // how many nodes to rotate        if( len<=1 || x==0) return head;            // find xth node from tail of list        ListNode *tmp=head;        ListNode *lend=head;        ListNode *hstart=head;        while(tmp->next){            if(x==0){                lend = lend->next;            }else{                --x;            }            tmp = tmp->next;        }                hstart = lend->next;        lend->next=NULL;        tmp->next=head;        return hstart;    }};

转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！


联系
我们