九江便宜做网站,网站怎么做分时,梧州零距离网论坛,如何设计网页模板【力扣】24. 两两交换链表中的节点
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
示例 1#xff1a; 输入#xff1a;hea…【力扣】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保存每次迭代的两个节点StackListNode 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;}
}
