题目描述
给你一个链表的头节点,和一个值k,请把链表的每个节点向右移动k个位置。
示例1:
链表 1—2---3—4---5,k为2,向右移动1个位置,链表变为:5—1---2—3---4,再移动1个位置,链表变为:4—5---1—2---3
示例2:
链表 1—2---3,k为4,向右移动1个位置,链表变为:3—1---2,移动2个位置,链表变为:2—3---1,移动3个位置,链表变为:1—2---3,
移动4个位置,链表变为:3—1---2
链表的问题,解法总是非常多,反正就是绕来绕去,最后能正确链上就可以了
解法1:
通过遍历k次,每一次遍历都完成一次尾节点的右移,最终实现题目要求
public ListNode revolve1(ListNode head, int k) {
//边界处理
if (head == null || head.next == null) {
return head;
}
//如果链表只有两个节点,那么偶数次旋转,实际上链表等于没变,奇数次旋转,则两个节点交换下即可
if (head.next.next == null) {
if ((k & 1) != 0) {
ListNode pre = head;
head = head.next;
head.next = pre;
pre.next = null;
}
return head;
}
for (int i = 0; i < k; i++) {
//每一次遍历先找到尾节点和尾节点的前一个节点
ListNode tail = head;
ListNode tailPre = null;
while (tail.next != null && tail.next.next != null) {
tailPre = tail.next;
tail = tail.next.next;
}
//尾节点的下一个节点指向头节点,尾节点的前一个节点指向null,头节点指向尾节点(此时的尾节点实际上已经是新的头节点了)
//(此处处理过程可以看图解)
tail.next = head;
tailPre.next = null;
head = tail;
}
return head;
}
tail.next = head;
tailPre.next = null;
head = tail;
解法2:
通过旋转链表的方式,让原本逆向的操作变成正向的操作,然后就可以从头节点开始直接操作即可。
public ListNode revolve2(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
//反转链表
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
//记录旋转之前链表的头节点
ListNode originalHead = head;
//现在我们可以正向的遍历链表,然后把每一个头节点,都移动到直接的头节点后面
//(此处处理过程可以看图解)
for (int i = 0; i < k; i++) {
ListNode next = pre.next;
originalHead.next = pre;
pre.next = null;
originalHead = pre;
pre = next;
}
//最后再反转回来即可
ListNode pre2 = null;
ListNode cur2 = pre;
while (cur2 != null) {
ListNode next = cur2.next;
cur2.next = pre2;
pre2 = cur2;
cur2 = next;
}
return pre2;
}
ListNode next = pre.next;
originalHead.next = pre;
pre.next = null;
originalHead = pre;
pre = next;
第二次遍历:
ListNode next = pre.next;
解法3:
快慢指针的方式,这种方式也可以经常用来解决需要反向操作链表的问题。
主要思想是,让快指针先走k次,然后慢指针再和快指针一起走,当快指针走完时,慢指针会刚好来到k的位置。此时慢指针的下一个节点就是新的头节点,慢指针当前的节点就是尾节点,最后把快指针当前的节点链上原来的头节点即可。
public ListNode revolve3(ListNode head, int k) {
//边界处理
if (k == 0 || head == null || head.next == null) {
return head;
}
//一个快指针,一个慢指针
ListNode fast = head;
ListNode slow = head;
//记录链表的长度
int len = 0;
while (len < k && fast != null) {
len++;
fast = fast.next;
}
/**
* 如果fast为null,则代表k的值大于链表的长度
* 那么实际上:当k值大于链表的长度时,旋转k次的结果等于旋转(k%链表的长度)次
* 比如:链表为: 1---2---3,k为:4
* k的长度要大于链表的长度,所以k=4%3,k=1,即整个链表实际上只需要旋转一次即可
*/
if (fast == null) {
k = k % len;
//如果k==0,则实际上不用旋转,直接返回即可
if (k == 0) {
return head;
}
//否则快指针从头开始,重新先走k次,此时的k已经是和len取模的结果了
fast = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
}
//此时,慢指针和快指针继续同时走
while (fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
//(此处处理过程可以看图解)
//当快指针走到底时,此时慢指针的下一个节点就是新的头节点
ListNode newHead = slow.next;
//慢指针当前节点就是尾节点
slow.next = null;
//快指针的下一节点(就是原来链表的最后一个节点)链上原来的头节点即可
fast.next = head;
//最后返回新的头节点
return newHead;
}
ListNode newHead = slow.next;
slow.next = null;
fast.next = head;
解法4:
比较正常的思路,先遍历一次链表,得到链表的长度,和链表的最后一个节点,有了链表的长度就可以直接遍历到(长度-k)的位置了,之后直接拼接下即可。
public ListNode revolve4(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
//计算链表的长度,顺便得到链表的最后一个节点
ListNode cur = head;
int len = 1;
while (cur.next != null) {
len++;
cur = cur.next;
}
//和第三种解法一样,对于k超过链表长度的问题,直接取模即可
int index = len - (k % len) - 1;
//(此处处理过程可以看图解)
//最后一个节点指向头节点,此时链表是一个环
cur.next = head;
//来到重新组装链表的位置
for (int i = 0; i < index; i++) {
head = head.next;
}
//head的next节点便是新的头节点,head自身便是尾节点
ListNode newHead = head.next;
//断开头尾节点
head.next = null;
return newHead;
}
cur.next = head;
for (int i = 0; i < index; i++) {
head = head.next;
}
遍历结束后,head来到节点3
ListNode newHead = head.next;
head.next = null;
总结:
解法1:因为每次都需要重新遍历整个链表,所以时间复杂度为O(n^2)
解法2:反转了两次链表,和一次遍历,也就相当于遍历了3次链表,虽然时间复杂度是O(n),不过常数项比较高
解法3:快慢指针的方式,遍历了链表2次,比解法2要优
解法4:也是遍历了2次,不过想比解法3,处理上明显要简单一些。
更多推荐
链表算法面试题---旋转链表
发布评论