给定链表的头节点,旋转链表,将链表每个节点往右移动 k 个位置,原链表后 k 个位置的节点则依次移动到链表头。
即,例如链表 : 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3
数据范围:链表中节点数满足 ,
class Solution { public: ListNode* rotateLinkedList(ListNode* head, int k) { int len=0; ListNode* address[1010]; ListNode *cur=head; while (cur) { address[len++]=cur; cur=cur->next; } if(len==0) return head; k%=len; address[len-k-1]->next=nullptr; address[len-1]->next=head; return address[len-k]; } };
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { if(head == null) return head; // 先求链表倒数第k个节点 ListNode cur = head; int n = 0; while(cur != null){ n ++; cur = cur.next; } k %= n; ListNode fast = head; for(int i = 0; i < k - 1; i++){ fast = fast.next; } ListNode slow = head; ListNode prev = new ListNode(-1); prev.next = slow; while(fast.next != null){ prev = prev.next; slow = slow.next; fast = fast.next; } prev.next = null; fast.next = head; return slow; } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { // write code here if (k == 0 || head == null) return head; ListNode tail = head; // 找到尾部 int length = 1; // 计算链表长度 while(tail.next!=null) { tail = tail.next; length++; } k = k % length; // 这里的操作是因为 k 可能大于length 所以要求余 ListNode newHeadPre = head; // 新链头的上一个位置 for (int i = 0; i < length - k - 1; i++) { newHeadPre = newHeadPre.next; } ListNode newHead = head; // 新链头 newHead = newHeadPre.next; // 更新新链头 newHeadPre.next = null; // 将新链头的上一个位置 设置位链尾 tail.next = head; // 将原本的链尾,接到老的链头上 return newHead; } }这个还是很好懂的
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { // write code here if (head == null || head.next == null) return head; ListNode slow = head, fast = head; ListNode preSlow = new ListNode(-1); preSlow.next = head; ListNode tmp = head; int cnt = 0; while (tmp != null) { tmp = tmp.next; cnt++; } k %= cnt; if (k == 0) return head; for (int i = 0; i < k - 1; i++) fast = fast.next; while (fast.next != null) { slow = slow.next; fast = fast.next; preSlow = preSlow.next; } // 断开 preSlow.next = null; // 拼接 fast.next = head; // 返回新头部 return slow; } }
/** * #[derive(PartialEq, Eq, Debug, Clone)] * pub struct ListNode { * pub val: i32, * pub next: Option<Box<ListNode>> * } * * impl ListNode { * #[inline] * fn new(val: i32) -> Self { * ListNode { * val: val, * next: None, * } * } * } */ struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ pub fn rotateLinkedList(&self, mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> { // write code here if head.is_none() {return head} let mut len = 0; let mut p = &head; while p.is_some() { p = &p.as_ref().unwrap().next; len += 1; } let mut skip = len - (k % len); if (k % len) == 0 {return head} drop(p); let mut p = &mut head; for _ in 1..skip { p = &mut p.as_mut().unwrap().next; } let mut newhead = p.as_mut().unwrap().next.take(); drop(p); let mut p = &mut newhead; while p.as_mut().unwrap().next.is_some() { p = &mut p.as_mut().unwrap().next; } p.as_mut().unwrap().next = head; newhead // todo!(); } }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { // write code here if(head == null){ return head; } int length = 0; ListNode fast = head; //统计链表长度 while(fast != null){ fast = fast.next; length++; } System.out.print(length); k = k % length; //移动次数和链表长度一致,就不用移动,直接返回链表即可 if(k == 0){ return head; } fast = head; ListNode slow = head; //快慢指针,fast先移动k步 while(k != 0){ fast = fast.next; k--; } while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next; } //此时fast在链表末尾,slow.next 指向要旋转的链表 ListNode node = slow.next; slow.next = null; fast.next = head; head = node; return head; } }
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def rotateLinkedList(self , head: ListNode, k: int) -> ListNode: # write code here l_len = 0 point = head while point is not None: l_len += 1 point = point.next if l_len == 0: return head k = k%l_len if k == 0: return head point = head next_point = point for i in range(k): next_point = next_point.next while next_point.next is not None: next_point = next_point.next point = point.next new_head = point.next point.next = None next_point.next = head return new_head
public ListNode rotateLinkedList(ListNode head, int k) { // write code here if (head == null) return null; ListNode len_acc = head; int len = 0; ListNode pre = head; ListNode tail = pre; //求链表长度,算旋转距离 while (len_acc !=null){ len++; len_acc = len_acc.next; } k = k%len; //找到距离为k的两个指针 while(k > 0){ tail = tail.next; k--; } //同时右移两个指针到链表末尾 while (tail.next != null){ pre = pre.next; tail = tail.next; } //重新连接链表 ListNode temp = head; head = pre.next; tail.next = temp; pre.next = null; return head; }
class Solution: def rotateLinkedList(self , head: ListNode, k: int) -> ListNode: if head == None: return head rare = head length = 1 while rare.next != None: rare = rare.next length = length + 1 rare.next = head step = length - k % length while step > 1: head = head.next step = step - 1 p = head head = head.next p.next = None return head
public ListNode rotateLinkedList (ListNode head, int k) { if (head == null || head.next == null || k <= 0) { return head; } int length = 1; ListNode curr = head; while (curr.next != null) { length++; curr = curr.next; } curr.next = head; k = k % length; if (k == 0) { return head; } for (int i = 0; i < length-k-1; i++) { head = head.next; } ListNode newHead = head.next; head.next = null; return newHead; }
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ //链表反转 ListNode* reverse(ListNode* head) { ListNode* h = new ListNode(0); ListNode* temp; while (head != nullptr) { temp = head; head = head->next; temp->next = h->next; h->next = temp; } return h->next; } ListNode* rotateLinkedList(ListNode* head, int k) { // write code here if(head==nullptr) return nullptr; int n = 0; int cnt = 0; //把整个链表反转 head = reverse(head); ListNode* h = head; //计算整个链表长度,因为k有可能大于n while (h != nullptr) { h=h->next; n++; } //k取模 k%=n; ListNode* end=head; while (end != nullptr) { cnt++; if (cnt == k) {//找到断开位置 break; } end=end->next; } //断开位置的下一个就是第二个链表的起始位置 ListNode* secondstart=end->next; //链表断开 end->next=nullptr; //对第一个链表进行反转 ListNode* first=reverse(head); ListNode* ans=first; //找到第一个链表的尾部(且不为空) while(first->next!=nullptr){ first=first->next; } //对第二个链表进行反转 secondstart=reverse(secondstart); //cout<<secondstart->val<<" "<<secondstart->next->val; //将第一个链表的尾部和第二个链表的头相连接 first->next=secondstart; return ans; } };
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* rotateLinkedList(ListNode* head, int k) { // write code here // 算出节点数量 ListNode* temp = head; int len = 0; while(temp) { temp = temp->next; ++len; } k %= len; if(k==0 || head==nullptr) return head; // 新链表头的前一个 ListNode* t_1 = head; // 新链表头 ListNode* t_2 = head; // 原来链表的最后一位 ListNode* t_3 = head; // 从下标 1 开始 int t = 1; while(t<len) { // 新链表头的前一个 if(t<len-k) t_1 = t_1->next; // 新链表头 if(t<=len-k) t_2 = t_2->next; // 原来链表的最后一位 t_3 = t_3->next; ++t; } // cout << t_1->val << ", " << t_2->val << ", " << t_3->val << endl; t_1->next = nullptr; t_3->next = head; return t_2; } };
public ListNode rotateLinkedList (ListNode head, int k) { // write code here ListNode res = new ListNode(0); res.next = head; ListNode fast = res; ListNode front = null; ListNode slow = res; ListNode cur = head; int length = 1; if ( head == null || head.next == null) return head; //判断链表长度 while (cur.next != null) { length++; cur = cur.next; } //对长度进行取余得到有效变换的长度 int j = k % length; for (int i = 0; i < j; i++) { fast = fast.next; } while (fast != null) { front = slow; slow = slow.next; fast = fast.next; } front.next = null; res.next = slow; while (slow.next != null) { slow = slow.next; } slow.next = head; return res.next; }
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { // write code here int num = getNodeNum(head); if (num == 0 || k % num == 0) return head; k = k % num; ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode fast = dummyHead; while (k-- > 0) { fast = fast.next; } ListNode slow = dummyHead; while (fast.next != null) { slow = slow.next; fast = fast.next; } ListNode rotateHead = slow.next; slow.next = null; fast.next = dummyHead.next; return rotateHead; } public int getNodeNum(ListNode head) { int res = 0; while (head != null) { res++; head = head.next; } return res; } }
if(head==NULL)//空链表的特殊情况 return head; struct ListNode * p=head; int length=0; while(p)//遍历链表求表长 { p=p->next; length++; } p=head; while(p->next)//遍历链表找到表尾 { p=p->next; } p->next=head;//使链表成为循环链表 p=head; for(int i=0;i<length-k%length;i++)//找到旋转后的表头 { p=p->next; } struct ListNode * result=p; for(int i=0;i<length-1;i++) { p=p->next; } p->next=NULL;//遍历新链表使表尾指针指空,接触循环链表 return result;
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode rotateLinkedList (ListNode head, int k) { // write code here if(head == null) return null; int i = 1; ListNode cur = head; int len = 0; while(cur.next != null){ cur = cur.next; len++; } len++; cur.next = head; while(i <= len - (k % len)){ cur = head; head = head.next; i++; } cur.next = null; return head; } }
package main import _"fmt" import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ func rotateLinkedList( head *ListNode , k int ) *ListNode { if head==nil{ return nil } arr:=[]*ListNode{} for p:=head;p!=nil;p=p.Next{ arr=append(arr,p) } n:=len(arr) k%=n arr=append(arr[n-k:],arr[:n-k]...) for i,p:=range arr{ if i+1<n{ p.Next=arr[i+1] }else{ p.Next=nil } } return arr[0] }