给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
- 链表中节点的数目在范围
[0, 100]
内 0 <= Node.val <= 100
解题思路:
首先设置一个头结点,方便统一操作。
设置cur指针从头结点开始向后遍历,
设置firstNode指针,指向cur后的第一个结点,
设置secondNode指针,指向cur后的第二个结点,
设置temp指针,指向secondNode后的结点,即cur后的第三个结点,用来保存下一步要成对交换的第一个结点。
交换时要理清顺序:
先把第二个结点移到第一个结点的位置,所以需要修改cur.next和secondeNode.next;
然后修改firstNode.next
交换完后,cur应该指向temp的前一个结点,此时的firstNode指针就是指向了temp的前一个结点,所以交换完后,cur的下一步应该到firstNode。
代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 设置一个头结点
ListNode Node = new ListNode(-1);
Node.next = head;
ListNode cur = Node; // cur指针初始指向头结点,从前向后遍历
ListNode firstNode = null; // 临时指针,保存cur后的第一个结点
ListNode secondNode = null; // 临时指针,保存cur后的第二个结点
ListNode temp = null; // 临时指针,保存cur后第二个结点的后一个结点
while(cur.next != null && cur.next.next != null) {
firstNode = cur.next;
secondNode = cur.next.next;
temp = cur.next.next.next;
cur.next = secondNode;
secondNode.next = firstNode;
firstNode.next = temp;
cur = firstNode; // cur往后移动
}
return Node.next;
}
}