LeetCode 328. 奇偶链表

题目描述

🔥 328. 奇偶链表

image-20220917134534684

思路分析

  1. 定义两个指针：使用两个指针 odd 和 even，分别指向奇数节点和偶数节点的头部。
  2. 遍历链表：通过一个循环遍历链表，将奇数节点和偶数节点分别连接。
  3. 连接奇偶链表：在遍历结束后，将奇数链表的尾部连接到偶数链表的头部。

我们可以使用两个指针分别指向奇数节点和偶数节点。遍历链表时，将奇数节点连接在一起，再将偶数节点连接在一起，最后将奇数链表和偶数链表连接起来。

  1. 初始化两个指针 odd 和 even，分别指向链表的头节点和第二个节点。
  2. 使用一个指针 evenHead 保存偶数链表的头节点，以便最后连接。
  3. 遍历链表，直到 even 或 even.Next 为 nil：
    • 将 odd.Next 指向 even.Next，然后将 odd 移动到下一个奇数节点。
    • 将 even.Next 指向 odd.Next，然后将 even 移动到下一个偶数节点。
  4. 最后，将 odd.Next 指向 evenHead，连接奇数链表和偶数链表。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

func oddEvenList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	odd := head
	even := head.Next
	evenHead := even // 保存偶数链表的头部

	// 遍历链表
	for even != nil && even.Next != nil {
		odd.Next = even.Next // 将奇数节点连接到下一个奇数节点
		odd = odd.Next       // 移动奇数指针
		even.Next = odd.Next // 将偶数节点连接到下一个偶数节点
		even = even.Next     // 移动偶数指针
	}

	odd.Next = evenHead // 将奇数链表和偶数链表连接
	return head
}

  • 时间复杂度：O(n)，其中 n 是链表的节点数。每个节点遍历一次。

  • 空间复杂度：O(1)，只使用了常量级的额外空间。

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/54921733
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！