LeetCode-61-旋转链表

题目

思路

1. 没什么好说的，刚开始没发现头结点是倒数第k个结点，还以为是k+1个结点，折腾了半天，发现了就好了。

代码

    public ListNode rotateRight(ListNode head, int k) {
        if(head==null) return null;
        if(k==0) return head;
        //倒数第k个节点为头结点
        int length = 0;
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null){
            length++;
            fast = fast.next;
        }
        k = k % length;
        //找到倒数第k个 快慢指针
        fast = head;
        for(int i=0;i<k;i++) fast = fast.next;
        //记录slow的pre 为断结点的地方
        ListNode pre = head;
        while (fast!=null){
            fast = fast.next;
            pre = slow;
            slow = slow.next;
        }
        if(slow == null){ // 说明直接连即可
            return head;
        }
        pre.next=null;
        //开始连
        ListNode new_head = new ListNode(0);
        new_head.next = slow;
        while (slow.next!=null) slow = slow.next;
        slow.next=head;
        return new_head.next;
    }
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