题目
题目来源leetcode
leetcode地址：24. 两两交换链表中的节点，难度：简单。
题目描述(摘自leetcode)：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 1： 输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2： 输入：head = [] 输出：[] 示例 3： 输入：head = [1] 输出：[1] 提示： 链表中节点的数目在范围 [0, 100] 内 0 <= Node.val <= 100
本地调试代码：
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) { ... } public static void main(String[] args) { ListNode node4 = new ListNode(4, null); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); //两两交换犯法调用 ListNode listNode = new Solution().swapPairs(node1); //遍历 printList(listNode); } private static void printList(ListNode listNode) { if(listNode == null){ return; } System.out.print("["); while(listNode != null){ System.out.print(listNode.val); if(listNode.next != null){ System.out.print(","); } listNode = listNode.next; } System.out.print("]"); } }
题解
NO1：三指针移动
思路：定义三个指针，每次两两交换后，统一移动三个指针，中间可能会比较绕一点，可搭配画图进行题解。
核心其实就是不断移动三个指针，之后来进行两两交换操作，中间注意一些边界条件即可。
代码：
public ListNode swapPairs(ListNode head) { //1个或0个节点直接返回 if(head == null || head.next == null){ return head; } //三个指针 ListNode preNode = null; ListNode firstNode = head; ListNode secNode = firstNode.next; //最终返回的头节点 ListNode newHead = secNode; //只有成对的才能够进行下面的操作 while(firstNode !=null && secNode != null){ //保存secNode的后一个节点 ListNode postNode = secNode.next; //反转节点 secNode.next = firstNode; firstNode.next = postNode; if(preNode!=null){ preNode.next = secNode; } //移动三个指针 preNode = firstNode;//第一个指针 if(postNode == null){ break; } firstNode = postNode;//第二个指针 if(postNode.next == null){ break; } secNode = postNode.next; } return newHead; }
NO2：虚拟头节点法
思路：定义一个虚拟节点后，之后的操作都是相同的，其中核心是以两个指针来进行节点之间的交换。
代码：
public ListNode swapPairs(ListNode head) { //虚拟节点 ListNode dummyNode = new ListNode(0, head); ListNode preNode = dummyNode; //该条件含义指的是：保证当前还有成对的进行反转。下面主要核心就是通过preNode、head两个指针来进行两两反转 while(preNode.next != null && preNode.next.next != null){ //临时保存第3个节点，之后反转链表指向第3个节点时有用 ListNode tempNode = head.next.next; //反转链表节点 preNode.next = head.next; head.next.next = head; head.next = tempNode; //移动指针 (注意此时的head与已反转) preNode = head; head = preNode.next; } return dummyNode.next; }
NO3：递归求解
思路：下面针对于递归题解进行部分问题解答
代码：
/** * 递归 * @param head * @return 上一组交换的下一个目标节点 */ public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } ListNode next = head.next; ListNode newNode = swapPairs(next.next); //反转链表，只负责当前两个节点指向 next.next = head; head.next = newNode; return next; }
