当前位置：首页 > news >正文

【力扣】24. 两两交换链表中的节点＜栈＞

news 2025/7/15 3:34:36

【力扣】24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 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 中拿出两个节点，再把这两个节点串联起来，重复这个逻辑遍历完整个链表，就可以做到两两反转的效果。

import java.util.*;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;}//用来指向新链表 dummyNodeListNode dummyNode = new ListNode(-1);ListNode prev = dummyNode;//用来入栈 出栈，走俩步ListNode cur = head;//用stack保存每次迭代的两个节点Stack<ListNode> stack = new Stack<>();while (cur != null && cur.next != null) {//将两个节点放入stack中stack.add(cur);stack.add(cur.next);//当前节点往前走两步cur = cur.next.next;//从stack中弹出两个节点，然后用 prev节点指向新弹出的两个节点//弹第一个prev.next = stack.pop();prev = prev.next;//弹第二个prev.next = stack.pop();prev = prev.next;}/*//注意边界条件，当链表长度是奇数时，cur就不为空if (cur != null) {prev.next = cur;}else {prev.next = null;}
*///不管cur是否为空都可以让prev.next指向cur。prev.next = cur;return dummyNode.next;}
}