来源:力扣(LeetCode)
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。 示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
[0, 100]
内0 <= Node.val <= 100
我们利用一个 stack,然后不断迭代链表,每次取出两个节点放入 stack 中,再从 stack 中拿出两个节点。 借助 stack 后进先出的特点,放进去的时候是 1,2 。拿出来的时候就是 2,1 两个节点了。 再把这两个节点串联起来,重复这个逻辑遍历完整个链表,就可以做到两两反转的效果了。
/**
* 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;
}
//用stack保存每次迭代的两个节点
Stack<ListNode> stack = new Stack<ListNode>();
ListNode p = new ListNode(-1);
ListNode cur = head;
//head指向新的p节点,函数结束时返回head.next即可
head = p;
while(cur!=null && cur.next!=null) {
//将两个节点放入stack中
stack.add(cur);
stack.add(cur.next);
//当前节点往前走两步
cur = cur.next.next;
//从stack中弹出两个节点,然后用p节点指向新弹出的两个节点
p.next = stack.pop();
p = p.next;
p.next = stack.pop();
p = p.next;
}
//注意边界条件,当链表长度是奇数时,cur就不为空
if(cur!=null) {
p.next = cur;
} else {
p.next = null;
}
return head.next;
}
}
这道题在于怎么交换之后链接之后的节点,还可以使用迭代和递归来解题,相比于迭代和递归来说,用栈来解题,比较清晰易懂