给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1:
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2:
输入：head = []
输出：[]
示例 3:
输入：head = [1]
输出：[1]
提示:
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
思路
迭代法
这道题两种解法, 先说比较简单的迭代法, 这种链表题目最好都建立一个虚拟头节点(dummy), 这样可以让头节点的操作和其他节点一样, 而不用为头节点单设计一种方法.
使用临时节点(current)指向dummy, 进入循环, 因为要交换的节点不包括虚拟节点, 所以循环条件应该是current.next != null || current.next.next != null
接下来在循环中交换current.next和current.next.next的位置即可. 需要注意的是在最后记得让current前进, 不然就变成死循环了.
递归
第二种方法是递归, 递归我一直不太会, 不过这道题的递归比较简单(在看了题解后).
思路是每次递归交换两个节点, 所以递归结束条件应该是head != null && head.next != null 若满足结束条件, 直接返回head(链表个数是单数时返回的是不用交换的那个节点, 链表个数是双数时返回的是null)
进入递归, head是第一个节点, newHead是第二个节点. 每次递归只交换这俩节点, 交换后newHead在前, head在后, 所以head.next = swapPairs(newHead.next); (也就是指向下一次递归后位置在前的节点)
然后使newHead.next = head, 就完成了交换. 最后返回新的链表头节点newHead即可.
大家难以理解可以画图模拟一下.
代码实现
迭代法
/**
* 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 dummy = new ListNode(-1, head);
ListNode current = dummy;
while(current.next != null && current.next.next != null) {
ListNode firstNode = current.next;
ListNode secondNode = current.next.next;
current.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;
current = firstNode;
}
return dummy.next;
}
}
递归法
/**
* 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 newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
}
}