[leetcode]Reorder List @ Python
2020-11-22 18:27
标签：des style blog class code java ext javascript color int rgb 原题地址：http://oj.leetcode.com/problems/reorder-list/ 题意： Given a singly linked
list L: L0→L1→…→Ln-1→Ln, You must do this in-place without altering the nodes‘ values. For example, 解题思路：1，先将链表截断为两个相等长度的链表，如果链表长度为奇数，则第一条链表长度多1。如原链表为L={1,2,3,4,5}，那么拆分结果为L1={1,2,3}；L2={4,5}。拆分的技巧还是快慢指针的技巧。 2，将第二条链表L2翻转，如将L2={4,5}翻转为L2={5,4}。 3，按照题意归并链表。 [leetcode]Reorder List @ Python,搜素材,soscw.com [leetcode]Reorder List @ Python 标签：des style blog class code java ext javascript color int rgb 原文地址：http://www.cnblogs.com/zuoyuan/p/3700846.html
reorder
it
to: L0→Ln→L1→Ln-1→L2→Ln-2→…
Given {1,2,3,4}, reorder it
to {1,4,2,3}.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return nothing
def reorderList(self, head):
if head==None or head.next==None or head.next.next==None: return head
# break linked list into two equal length
slow = fast = head #快慢指针技巧
while fast and fast.next: #需要熟练掌握
slow = slow.next #链表操作中常用
fast = fast.next.next
head1 = head
head2 = slow.next
slow.next = None
# reverse linked list head2
dummy=ListNode(0); dummy.next=head2 #翻转前加一个头结点
p=head2.next; head2.next=None #将p指向的节点一个一个插入到dummy后面
while p: #就完成了链表的翻转
tmp=p; p=p.next #运行时注意去掉中文注释
tmp.next=dummy.next
dummy.next=tmp
head2=dummy.next
# merge two linked list head1 and head2
p1 = head1; p2 = head2
while p2:
tmp1 = p1.next; tmp2 = p2.next
p1.next = p2; p2.next = tmp1
p1 = tmp1; p2 = tmp2
文章标题：[leetcode]Reorder List @ Python
文章链接：http://soscw.com/index.php/essay/22106.html