网站seo快速排名,做PPT的网站canva,wordpress激活码,网站建设公司中企动力题目要求#xff1a;给定链表的头结点#xff0c;旋转链表#xff0c;将链表每个节点向右移动K个位置。 示例#xff1a; 输入#xff1a;head [1,2,3,4,5], k2 输出#xff1a;[4,5,1,2,3]
双指针思想#xff1a; 先用双指针策略找到倒数K的位置#xff0c;也就是(…题目要求给定链表的头结点旋转链表将链表每个节点向右移动K个位置。 示例 输入head [1,2,3,4,5], k2 输出[4,5,1,2,3]
双指针思想 先用双指针策略找到倒数K的位置也就是(1,2,3)和4,5)两个序列之后再将两个链表拼接成(4,5,1,2,3}就行了。 具体思路是: 因为k有可能大于链表长度所以首先获取一下链表长度len如果然后kk % len如果k 0则不用旋转直接返回头结点。否则: 1、快指针先走k步 2、慢指针和快指针一起走 3、快指针走到链表尾部时慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部慢指针指向的节点断开和下一节点的联系 4、返回结束时慢指针指向节点的下一节点
import java.util.*;public class RotateRight_旋转数组 {public static void main(String[] args) {//int[] a {1, 2, 3, 4, 5};ArrayListInteger lst new ArrayList();//输入Scanner scanner new Scanner(System.in);String s scanner.nextLine();Scanner input new Scanner(s);while(input.hasNextInt()){lst.add(input.nextInt());}Integer[] a lst.toArray(new Integer[lst.size()]);ListNode nodeA initLinkedList(a); //数组初始化为链表ListNode nodeB initLinkedList2(lst); //集合初始化为链表ListNode node rotateRight(nodeB, 2); //开始旋转System.out.println(toString(node));}//定义链表节点static class ListNode{public int val;public ListNode next;ListNode(int x){val x;next null;}}//数组初始化链表public static ListNode initLinkedList(Integer[] a){ListNode head null, cur null;for (int i 0; i a.length; i){ListNode newNode new ListNode(a[i]);if (i0){head newNode;cur newNode;}else{cur.next newNode;cur cur.next;}}return head;}//集合初始化链表public static ListNode initLinkedList2(ArrayList a){ListNode head null, cur null;for (int i 0; i a.size(); i){ListNode newNode new ListNode((Integer) a.get(i));if (i0){head newNode;cur newNode;}else{cur.next newNode;cur cur.next;}}return head;}//开始旋转public static ListNode rotateRight(ListNode head, int k) {if (head null || k 0) {return head;}ListNode temp head;ListNode fast head;ListNode slow head;int len 0;//链表的长度while (head ! null) {head head.next;len;}//如果能整除则直接返回该链表if (k % len 0) {return temp;}while ((k % len) 0) {k--;fast fast.next;}while (fast.next ! null) {fast fast.next;slow slow.next;}ListNode res slow.next;slow.next null;fast.next temp;return res;}//输出链表public static String toString(ListNode head) {ListNode current head;//StringBuilder可以用来拼接字符串StringBuilder sb new StringBuilder();while(current !null){sb.append(current.val).append(\t);current current.next;}return sb.toString();}}
