首页 > 代码库 > [Leetcode] Rotate List

[Leetcode] Rotate List

2024-08-02 10:23:44   220人阅读

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.

 

Solution 1:

首先从head开始跑，直到最后一个节点，这时可以得出链表长度len。然后将尾指针指向头指针，将整个圈连起来。

这个既然要rotate，不如先连起来loop，这样怎么也不怕null pointer exception了。然后再找到该断开的地方断开。

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode rotateRight(ListNode head, int n) {14         if(head==null||head.next==null)15             return head;16         ListNode temp=head;17         int count=1;18         while(temp.next!=null){19             count++;20             temp=temp.next;21         }22         temp.next=head;23         n%=count;24         ListNode p=head;25         for(int i=0;i<count-n-1;i++){26             p=p.next;27         }28         temp=p.next;29         p.next=null;30         return temp;31     }32 }

 

Solution 2:

利用快慢指针来做。

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode rotateRight(ListNode head, int n) {14         if(head==null||head.next==null)15         return head;16         ListNode dummy=new ListNode(-1);17         dummy.next=head;18         ListNode fast=dummy;19         ListNode slow=dummy;20         ListNode temp=head;21         int count=1;22         while(temp.next!=null){23             count++;24             temp=temp.next;25         }26         n%=count;27         while(fast.next!=null&&n!=0){28             fast=fast.next;29             n--;30         }31         if(n!=0||fast.next==null)32             return dummy.next;33         while(fast.next!=null){34             fast=fast.next;35             slow=slow.next;36         }37         fast.next=dummy.next;38         dummy.next=slow.next;39         slow.next=null;40         41         return dummy.next;42     }43 }

 

[Leetcode] Rotate List


联系
我们