分别用单链表和双向链表编写关于交换相邻两个节点的代码
时间: 2024-09-22 09:01:48 浏览: 25
在单链表中交换相邻两个节点通常涉及到三个步骤:首先,找到需要交换的两个节点;其次,将它们的数据暂存;最后,更新这两个节点的指针指向对方。这里是一个简单的Python示例,假设`ListNode`是链表节点的类:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swap_nodes(head):
if not head or not head.next:
return head
# 指向当前节点的前一个节点
prev = None
current = head
# 指向当前节点的下一个节点
next_node = current.next
# 当前节点和下一个节点互换数据
temp_data = current.val
current.val = next_node.val
next_node.val = temp_data
# 如果下一个节点还有下一个,更新其指针
if next_node.next:
next_node.next = current.next
# 更新当前节点的指针
if prev:
prev.next = next_node
else:
head = next_node
return head
```
对于双向链表(`DoublyListNode`),因为每个节点都有指向前一个节点的引用,代码会稍作调整:
```python
class DoublyListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
def swap_nodes_in_doubly_linked_list(head):
if not head or not head.next:
return head
curr = head
prev = None
next_node = curr.next
temp_data = curr.val
curr.val = next_node.val
next_node.val = temp_data
# 更新指针
if curr.prev:
curr.prev.next = next_node
else:
head = next_node
next_node.prev = curr
curr.next = next_node.next
if next_node.next:
next_node.next.prev = curr
return head
```