(LeetCode 面试经典 150 题) 61. 旋转链表 （链表）

题目：61. 旋转链表

思路：链表，时间复杂度0(n)。

C++版本：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */classSolution{public: ListNode*rotateRight(ListNode* head,int k){if(head==nullptr|| head->next==nullptr|| k==0)return head;int n=1; ListNode * cur=head;// 统计完链表的节点数while(cur->next!=nullptr){ n++; cur=cur->next;}// 整个原始字符串= 左部分+右部分// 变化后的字符串= 右部分+左部分// ans就是左部分的数量int ans=n-k%n;// 将最后一个连到第一个节点 cur->next=head;//开始找左部分的最后一个点while(ans--){ cur=cur->next;}// tmp就是右部分的第一个节点 ListNode * tmp=cur->next; cur->next=nullptr;return tmp;}};

JAVA版本：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */classSolution{publicListNoderotateRight(ListNode head,int k){if(head==null|| head.next==null|| k==0)return head;int n=1;ListNode cur=head;while(cur.next!=null){ n++; cur=cur.next;}int ans=n-k%n; cur.next=head;while(ans>0){ ans--; cur=cur.next;}ListNode tmp=cur.next; cur.next=null;return tmp;}}

GO版本：

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcrotateRight(head *ListNode, k int)*ListNode {if k==0|| head==nil|| head.Next==nil{return head } n:=1 cur:=head for cur.Next!=nil{ n++ cur=cur.Next } ans:=n-k%n cur.Next=head for ans>0{ ans-- cur=cur.Next } tmp:=cur.Next cur.Next=nilreturn tmp }