0%

leetcode之旅-61-旋转链表

Posted on Edited on In

1. 题目描述（中等难度）

题目描述

  • 概述：涉及到倒数第几个节点的问题。我的思路是将问题转化为正数第几个的问题，或使用快慢指针。

    2. 我的解法

思路：

  • 先得到链表的节点数，即节点长度
  • 再计算旋转点是正数的第几个数。
  • 计算新的k值，忽略重复旋转的次数
  • 如果最后k==0，说明无需旋转，直接输出。
  • 设置pre指针。pre的next指向需要旋转的链表的第一个节点。将他们整体移到首部
    问题：我的解法太过复杂，在计算链表长度时，可以保存链表的尾指针，这样在第二遍循环时，就不用寻找了。
1
/**
2
 * Definition for singly-linked list.
3
 * public class ListNode {
4
 *     int val;
5
 *     ListNode next;
6
 *     ListNode(int x) { val = x; }
7
 * }
8
 */
9
class Solution {
10
    public ListNode rotateRight(ListNode head, int k) {
11
        if(head==null)return null;//如果链表为空
12
        //先计算节点数量
13
        ListNode l1=head;
14
        int dotnum=0;
15
        while(l1!=null)
16
        {
17
            dotnum++;
18
            l1=l1.next;
19
        }
20
        //倒转
21
        if(k>=dotnum)
22
            k=k%dotnum;
23
        if(k==0) return head//0属于特判，相当于没有反转，之前没有考虑到
24
        ListNode pre=head;
25
        int rotalteindex=dotnum-k;// 计算可得，pre的下一个节点就是要倒转的序列
26
        while(pre!=null)
27
        {
28
            if(rotalteindex==1)
29
            {
30
                ListNode ro=pre.next;
31
                pre.next=null;
32
                pre=ro;
33
                while(ro.next!=null)//找到旋转链表的尾部指针，使其直接指向总链表的head
34
                 ro=ro.next;
35
                ro.next=head;
36
                head=pre;//更新head
37
                break;
38
            }
39
            pre=pre.next;
40
            rotalteindex--;
41
        }
42
        return head;
43
    }
44
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
    解决问题：
    1
    /**
    2
     * Definition for singly-linked list.
    3
     * public class ListNode {
    4
     *     int val;
    5
     *     ListNode next;
    6
     *     ListNode(int x) { val = x; }
    7
     * }
    8
     */
    9
    class Solution {
    10
        public ListNode rotateRight(ListNode head, int k) {
    11
            if(head==null)return null;
    12
            //先计算节点数量
    13
            ListNode l1=head;
    14
            ListNode tail=l1;
    15
            int dotnum=0;
    16
            while(l1!=null)
    17
            {
    18
                dotnum++;
    19
                tail=l1;//记录尾指针
    20
                l1=l1.next;
    21
    22
            }
    23
            //倒转
    24
            if(k>=dotnum)
    25
                k=k%dotnum;
    26
            if(k==0) return head;//0属于特判，相当于没有反转，之前没有考虑到
    27
            ListNode pre=head;
    28
            int rotalteindex=dotnum-k;// 计算可得，pre的下一个节点就是要倒转的序列
    29
            while(pre!=null)
    30
            {
    31
                if(rotalteindex==1)
    32
                {
    33
                    ListNode ro=pre.next;
    34
                    pre.next=null;
    35
                    tail.next=head;//直接使用尾指针
    36
                    head=ro;
    37
                    break;
    38
                }
    39
                pre=pre.next;
    40
                rotalteindex--;
    41
            }
    42
            return head;
    43
        }
    44
    }

    3方法二：

    这道题不能直接使用快慢指针，不求链表总长，因为k是一个任意大的数，存在重复旋转的问题。
    如果k<=链表总长，那么可以直接用快慢指针
    1
    class Solution {
    2
        public ListNode rotateRight(ListNode head, int k) {
    3
            if(head==null)return null;
    4
           //利用快慢指针
    5
           ListNode first=head;
    6
           ListNode second=head;
    7
           for(int i=0;i<k;i++)
    8
                first=first.next;
    9
            while(first.next!=null)//使快指针最后指向尾节点
    10
            {
    11
                first=first.next;
    12
                second=second.next;
    13
            }
    14
            ListNode newhead=second.next;
    15
            second.next=null;
    16
            first.next=head;
    17
            head=newhead;
    18
            return newhead;
    19
        }
    20
    }

    4 总结

    对于针对链表中倒数第n个节点的问题，可以使用快慢指针或先求链表总长len，在计算节点正数的顺序。使用第一中方法的前提是k<=len.