Rotate List, Leetcode 解题笔记

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必须小于list的长度,于是想用two pointer做。后来发现题目本意是k可以超过list的长度。于是用下面的方法:
首先从head开始跑,直到最后一个节点,这时可以得出链表长度len。然后将尾指针指向头指针,将整个圈连起来,接着往前跑len – k%len,从这里断开,就是要求的结果了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) 
    {
        if (head == null || n == 0) { return head; }
        
        ListNode lastEle = head;
        int length = 1;
        while (lastEle.next != null) {
            lastEle = lastEle.next;
            length ++;
        }
        
        n = n % length;
        lastEle.next = head;
        ListNode cur = head;
        for (int i=0; i<length-n-1; i++) {
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;
        return head;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s