旋转链表-双指针思想-LeetCode61

题目要求：给定链表的头结点，旋转链表，将链表每个节点向右移动K个位置。
示例：
输入：head = [1,2,3,4,5], k=2
输出：[4,5,1,2,3]

双指针思想：
先用双指针策略找到倒数K的位置，也就是(1,2,3)和4,5)两个序列，之后再将两个链表拼接成(4,5,1,2,3}就行了。
具体思路是:
因为k有可能大于链表长度，所以首先获取一下链表长度len，如果然后k=k % 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};
        ArrayList<Integer> 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 (i==0){
                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 (i==0){
                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();
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118