[Leetcode] 61.旋转链表

2018-09-06 23:46:40 +08:00
 Acceml

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

题解

昨晚吃火锅吃撑了回来这道题,还算顺利~~ 链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环,然后再切开就可以完成了。

python 版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        # 链表的节点个数
        count = 1
        cur = head
        while cur.next:
            count += 1
            cur = cur.next
        # 如果恰好走了一个环,就直接返回
        k = k % count
        if k == 0:
            return head
        cur.next = head
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        # 需要走 count-k 个,然后把链表切断
        for _ in range(count - k):
            prev = prev.next
        # 重新组成新的链表
        cur = prev.next
        new_head = cur
        
        prev.next = None

        return new_head

java 版本

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        int count = 1;
        ListNode cur = head;
        while (cur.next != null) {
            count++;
            cur = cur.next;
        }
        k = k % count;
        if (k == 0) {
            return head;
        }
        cur.next = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < count - k; i++) {
            prev = prev.next;
        }
        cur = prev.next;
        prev.next = null;
        return cur;
    }
}

热门阅读

1335 次点击
所在节点    程序员
1 条回复
qwertyegg
2018-09-08 08:42:19 +08:00
对空间要求不高直接扔到 stack 里面再吐出来好了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/486949

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX