链表奇偶链表优化（双指针分离）——LeetCode算法挑战
在LeetCode等在线编程平台上，链表操作是常见的算法题目类型之一。其中，“奇偶链表”问题是一个典型的链表操作问题，要求将链表中的节点按照奇偶位置进行分离，并重新组合成一个新链表。本文将围绕这一主题，通过双指针分离的方法，对奇偶链表问题进行优化，并详细解析其实现过程。
问题分析
给定一个链表的头节点`head`，要求将链表中的节点按照奇偶位置进行分离，并重新组合成一个新链表。具体要求如下：
1. 奇数位置的节点组成一个链表，偶数位置的节点组成另一个链表。
2. 两个链表中的节点顺序保持不变。
3. 如果原链表长度为奇数，则最后一个节点应该属于奇数链表。
双指针分离方法
为了实现奇偶链表的分离，我们可以使用双指针方法。具体步骤如下：
1. 创建两个指针`odd`和`even`，分别指向奇数链表和偶数链表的头节点。
2. 创建两个指针`odd_next`和`even_next`，分别指向奇数链表和偶数链表的下一个节点。
3. 遍历原链表，对于每个节点，根据其位置将其连接到奇数链表或偶数链表。
4. 遍历结束后，将奇数链表的最后一个节点指向偶数链表的头节点。
代码实现
以下是用Python语言实现的奇偶链表分离代码：
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head or not head.next:
return head
odd, even, even_head = head, head.next, head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
测试代码
def print_list(node):
while node:
print(node.val, end=" ")
node = node.next
print()
创建测试链表
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print("Original List:")
print_list(head)
分离奇偶链表
new_head = oddEvenList(head)
print("Odd List:")
print_list(new_head)
print("Even List:")
print_list(new_head.next)
代码解析
1. `ListNode`类定义了链表节点的数据结构，包含值`val`和指向下一个节点的指针`next`。
2. `oddEvenList`函数实现了奇偶链表的分离。判断链表是否为空或只有一个节点，如果是，则直接返回原链表。
3. 初始化`odd`、`even`和`even_head`指针，分别指向奇数链表的头节点、偶数链表的头节点和偶数链表的头节点。
4. 遍历原链表，将奇数位置的节点连接到奇数链表，偶数位置的节点连接到偶数链表。
5. 遍历结束后，将奇数链表的最后一个节点指向偶数链表的头节点。
6. 测试代码创建了测试链表，并调用`oddEvenList`函数进行奇偶链表分离，最后打印出奇数链表和偶数链表。
总结
本文通过双指针分离方法，实现了LeetCode上的奇偶链表问题。该方法具有以下优点：
1. 时间复杂度为O(n)，空间复杂度为O(1)。
2. 代码简洁易懂，易于理解和实现。
在实际应用中，我们可以根据具体需求对代码进行优化和改进。希望本文对您有所帮助！
Comments NOTHING