Leetcode 61. Rotate List （反转链表）

2019-11-06 07:36:37

字体：大中小

来源：转载

供稿：网友

LeetCode 61.RotateList

一、题目描述

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

二、解题思路

1.思路一：

（1）分别反转链表的左右部分（2）然后再反转整个链表

2.思路二

（1）将3–>4的指针断开（2）将5指向1

三、代码实现

思路二代码实现，时间复杂度O(n),空间复杂度O(1).

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */public class Solution { public int lengthOfList(ListNode head) { ListNode p = head; int n = 0; while(p!=null){ n++; p = p.next; } return n; } public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) { return head; } else { int n = lengthOfList(head); if (k >= n) { k = k % n; } if (k == 0){ return head; } //1 2 3 4 5 ListNode PRe = head; int index = 1; while (index < n - k){ pre = pre.next; index++; } ListNode newHead = pre.next; ListNode last = newHead; while (last.next != null) { last = last.next; } pre.next = null; last.next = head; return newHead; } }}

上一篇：LeetCode 2. Add Two Numbers

下一篇：多线程的实现方法