Leetcode 328

Posted on | | 阅读数
Words count in article: 290 | Reading time ≈ 1

Question

Solution1

首先，排除空，只有一个结点和只有两个结点的情况，直接返回head。

然后创建两个指针，pre和cur。pre指向排序好的奇数部分的末位元素，cur指向未被排序的奇数的前一位。每次交换，都将cur.next放入pre.next的位置。然后串联起来其他部分数据。

需要注意，在每次循环开始前，都要保存cur.next和pre.next，防止丢失。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not (head and head.next and head.next.next):
            return head
        pre = head
        cur = pre.next
        while cur and cur.next:
            temp1 = cur.next
            temp2 = pre.next
            pre.next = temp1
            cur.next = temp1.next
            temp1.next = temp2
            cur = cur.next
            pre = pre.next
        return head

Solution2

考虑创建一个偶数的链表，然后最后将两个链表连接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not (head and head.next):
            return head
        cur = head
        evenhead = head.next
        even = evenhead
        while even:
            cur.next = even.next
            if cur.next:
                cur = cur.next
                even.next = cur.next
                even = even.next
            else:
                break
        cur.next = evenhead
        return head