首页 > 代码库 > leetcode 【 Reorder List 】python 实现
leetcode 【 Reorder List 】python 实现
题目:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→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 实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。