Given a linked list, swap every two adjacent nodes and return its head.
说人话:
将链表中元素每两个交换一下。
举例:
本题是比较复杂的穿针引线。首先我们需要定义 4 个指针:
交换过程如下图:
pre->next = node2
node2.next = node1
node1.next = next;
拉直后:
交换后继续往后交换:
p = node1
当没有下一轮需要交换的时候(pre.next == null)就完成了。
/** * 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 dummyHead = new ListNode(0,head); //前一个节点 ListNode pre = dummyHead; //穿针引线 while(pre.next != null){ //第一个节点 ListNode node1 = pre.next; if(node1 == null){ break; } //第二个节点 ListNode node2 = node1.next; if(node2 == null){ break; } //下一结点 ListNode next = node2.next; //交换 pre.next = node2; node2.next = node1; node1.next = next; pre = node1; } return dummyHead.next; } }