您现在的位置是:首页 >学无止境 >leetcode-328 奇偶链表网站首页学无止境
leetcode-328 奇偶链表
简介leetcode-328 奇偶链表
题目如下:
给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。
请注意,偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例如下:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
提示:
- n == 链表中的节点数
- 0 <= n <= 104
- -106 <= Node.val <= 106
算法思路
官方题解我不知道它是怎么做的,反正我是这样做的。直接在在原链表head进行修改即可。
如果链表的节点的超过2个,那么把之后索引下标为奇数的节点连接在head的第一个节点后面(做完之后把对应的指针后移),把索引下标为偶数的节点连接在head的第二个节点后面(做完之后把对应的指针后移),直到到达最后一个节点即可。
图解如下(第5个元素没有画):
实现代码如下(Python):
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = head
count = 1
p1 = None
last = None
while p:
next = p.next
p.next = None
if count == 1:
p1 = p
elif count == 2:
p1.next = p
last = p1.next
else:
if count % 2 != 0:
p2 = p1.next
p1.next = p
p1 = p1.next
p1.next = p2
else:
last.next = p
last = last.next
p = next
count += 1
return head
if __name__ == '__main__':
a = Solution()
head = ListNode(1, ListNode(2,ListNode(3, ListNode(4,ListNode(5,None)))))
a.oddEvenList(head)
运行结果:
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。