24. 两两交换链表中的节点
不会写
① 题目的理解
“两两交换其中相邻的节点”,并不是简单地交换数据,而是交换整个节点。
题目 “两两” 隐含的要考虑节点个数奇偶问题。
② 节点交换的实现
引入虚拟头结点dummyhead。
引入cur指针对链表进行操作,如果用dummyhead 操作,最后指针的头节点的地址没有保存。
按照图示顺序进行处理(这三条线的顺序打乱可以吗?)
【虚拟头节点指向2】cur.next = cur.next.next;
【2指向1】此时2是cur.next ,但是1已经不知道是什么了,原本1是cur.next,但上一步改变了cur.next的指向。所以在上一步之前需要一个变量temp存储1的地址。
【1指向3】3这个地址也需要保存
比较简单的做法就是 引入: first指第一个节点,second指第二个节点,temp,指second下一个,cur临时变量。
③ 代码(java)
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyhead = new ListNode(0,head);
ListNode cur = dummyhead;
ListNode first,second,temp;
while(cur.next != null && cur.next.next != null) {
//cur.next == null 偶数个
//cur.next.next == null 奇数个
first = cur.next;
second = cur.next.next;
temp = second.next;//可以等于null,不会出错
cur.next = second;
second.next = first;
first.next = temp;
cur = first;
}
return dummyhead.next;
}
}