题目
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
思路
创建虚拟头节点,画图,确认步骤。
实现
/**
* 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) {
if(head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
ListNode p = dummy;
dummy.next = head;
ListNode i = head;
ListNode j = head.next;
// i 是第一个节点 j是第二个节点
//一轮下来 i!=null 且 j != null 就可以进行循环
while(i !=null && j != null){
ListNode temp = j.next;
//实际的交换步骤
p.next = j;
j.next = i;
i.next = temp;
p = i;
i = temp;
//这里是为了防止下面出现NPE。
//当移动指针准备下一轮循环的时候,发现第一个已经是null,可以直接返回退出循环了
if(i == null){
continue;
}
j = temp.next;
}
return dummy.next;
}
}