Java教程

力扣61(java&python)-旋转链表(中等)

本文主要是介绍力扣61(java&python)-旋转链表(中等),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:

给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。

示例1:

输入:head = [1,2,3,4,5], k = 2

输出:[4,5,1,2,3]

示例2:

 输入:head = [0,1,2], k = 4

输出:[2,0,1]

提示:

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

解题思路:

快慢指针+闭环

整体思路:找到倒数第k个结点的前一个结点,然后让链表的尾结点连接首结点形成闭环,然后倒数第k个结点是新链表的头结点,它之前的前一个结点作为链表的尾结点。

 具体思路(结合例子):

1.定义慢指针slow和快指针fast,初始都指向链表的头结点;

 2.让快指针走到链表的尾结点处,计算出链表的长度len,将尾结点指向head形成闭环;

 3.计算出慢指针需要移动的步数step,移动慢指针,移动step - 1步,使慢指针在倒数第k个结点的前一个结点;

 4.保存慢指针slow的下一个结点,作为新链表的头结点,并断开它与下一个结点的联系,使其指向空,让它作为新链表的尾结点;

 

 5.返回新的头结点即可。

注解:

1.len从1开始:因为快指针初始化的时候就在头结点上,因此长度初始值就应该为1。

2.对下断代码的解释:结合上面的例子,算出来的slow的步数step=5,但是实际slow只移动4步,因为链表是环形,需要把结点4和结点4的前一个结点断开,但是不清楚结点4的前一个结点是谁,故这里就少移动一步,指向结点3,并保存结点4,方便后面断开3和4的联系。

  while(step-- > 1){
            slow = slow.next;
        }

java代码:

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode rotateRight(ListNode head, int k) {
13         //特判
14         if(head == null || k == 0) return head;
15         int len = 1;
16         ListNode fast = head, slow = head;
17         //计算链表长度
18         while(fast.next != null){
19             len++;
20             fast = fast.next;
21         }
22         //将链表变成环
23         fast.next = head;
24         //计算出慢指针需要移动的步数
25         int step = len - k%len;
26         while(step-- > 1){
27             slow = slow.next;
28         }
29         //保存慢指针的下一个结点(新的头结点)
30         ListNode newHead = slow.next;
31         //断开闭环
32         slow.next = null;
33         return newHead;
34     }
35 }

 python3代码:

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, val=0, next=None):
 4 #         self.val = val
 5 #         self.next = next
 6 class Solution:
 7     def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
 8         # 特判当k为0或者链表长度为0或1
 9         if not head or not head.next or k == 0:
10             return head
11         # 定义快慢指针和长度
12         fast, slow = head, head
13         len = 1
14         # 计算链表长度
15         while fast.next:
16             len += 1
17             fast = fast.next
18 
19         #形成闭环
20         fast.next = head
21 
22         # 移动慢指针
23         step = len - k%len - 1
24         # 条件是当step为0停止循环,故step要先减1
25         while step:
26             slow = slow.next
27             step -= 1
28         # 保存当前慢指针等下一个结点作为新的头结点
29         newHead = slow.next
30         slow.next = None
31         return newHead

这篇关于力扣61(java&python)-旋转链表(中等)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!