程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Rotate List

LeetCode Rotate List

編輯:關於C++

LeetCode解題之Rotate List


原題

將一個鏈表中的元素向右旋轉k個位置。

注意點:

k可能非常大 最好不要申請額外空間

例子:

輸入: list = 1->2->3->4->5->NULL, k = 2

輸出: 4->5->1->2->3->NULL

解題思路

如果能有鏈表的長度,就不用擔心k非常大而不斷的循環旋轉了。所謂的旋轉其實就是在鏈表中間斷開,首尾相連。在獲取鏈表長度的時候順便把鏈表的首尾連起來。注意斷開的位置是在倒數第k個之前。

AC源碼

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

    def myprint(self):
        print(self.val)
        if self.next:
            self.next.myprint()


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return []
        curr = head
        length = 1
        while curr.next:
            curr = curr.next
            length += 1
        curr.next = head
        cur = head
        shift = length - k % length
        while shift > 0:
            curr = curr.next
            shift -= 1
        result = curr.next
        curr.next = None
        return result


if __name__ == "__main__":
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l5 = ListNode(5)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l5
    result = Solution().rotateRight(l1, 2)
    result.myprint()
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved