[Leetcode]328: Odd Even Linked List

Link : https://leetcode.com/problems/odd-even-linked-list/

Problem : Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.The first node is considered odd, and the second node is even, and so on.
有一個單項 linklist 需要reorder,把所有奇數node按順序接在一起,偶數node按順序接在一起,然後奇數 linklist 放前面,偶數 linklist放後面接起來。

Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.

圖來自leetcode

Thoughts :
1. 把奇數node接起來,linklist變成 1->3->5->7
2. 把偶數node接起來,linklist變成 2->4->6->8
3. 把奇數linklist跟偶數linklist接起來

Solution :

Time Complexity : O(n)
# one while loop -> n

Space Complexity : O(1)
每次執行都執行都建立一樣的個數的變數,也就是說每次執行都是耗費一樣的記憶體空間,所以是O(1)。

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store