首页 > 代码库 > leetcode 【 Reorder List 】python 实现

leetcode 【 Reorder List 】python 实现

题目:

Given a singly linked list LL0→L1→…→Ln-1→Ln,
reorder it to: L0→LnL1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes‘ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

 

代码: oj 测试通过 248 ms

 1 # Definition for singly-linked list. 2 # class ListNode: 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.next = None 6  7 class Solution: 8     # @param head, a ListNode 9     # @return nothing10     def reorderList(self, head):11         if head is None or head.next is None or head.next.next is None:12             return head13         14         dummyhead = ListNode(0)15         dummyhead.next = head16         17         # get the length of the linked list18         p = head19         list_length = 020         while p is not None:21             list_length += 122             p = p.next23         24         #reverse the second half linked list25         fast = dummyhead26         for i in range((list_length+1)/2):27             fast = fast.next28         pre = fast29         curr = pre.next30         for i in range( (list_length)/2 - 1 ):31             tmp = curr.next32             curr.next = tmp.next33             tmp.next = pre.next34             pre.next = tmp35         36         #merge37         h2 = pre.next38         fast.next = None # cut the connection between 1st half linked list and 2nd half linked list39         while head is not None and h2 is not None:40             tmp = head.next41             head.next = h242             tmp2 = h2.next43             head.next.next = tmp44             h2 = tmp245             head = tmp46         47         return dummyhead.next

思路

这道题的路子分三块:

1. 遍历单链表 求链表长度

2. 锁定后半个链表,反转后半个链表的每个元素

3. 切断前后半个链表的链接处 然后合并两个链表

leetcode 【 Reorder List 】python 实现