苏州营销型网站建设方法,电子商务网站建设用什么软件,做网站移交资料,如何设计公司网站#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计 ⛺️稳中求进#xff0c;晒太阳 题目 给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本… 个人主页五敷有你 系列专栏算法分析与设计 ⛺️稳中求进晒太阳 题目 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例
示例 1 输入head [1,2,3,4]
输出[2,1,4,3]示例 2
输入head []
输出[]示例 3
输入head [1]
输出[1]
思路 这里我们需要三个指针pqtemp。 假设链表是 1-2-3-4-5-6 在迭代的时候每次处理两个节点于是第一轮 p指向 1q 指向 2。 第二轮的时候 p 指向 3q 指向 4。第三轮的时候 p 指向 5q 指向 6。 我们通过 a.next b.next以及b.nexta就把两个指针的位置反转了于是1-2就变成2-1。 但这里有一个细节需要处理当我们第二轮迭代的时候p 指向 3q 指向 4。按照题目要求最终应该是2-1-4-3。也就是节点 1 需要跟节点 4 串起来只有两个指针就没法弄了所以需要第三个指针 tmp用来记录上一轮 p 的位置然后下一轮迭代的时候将原先的 p(也就是节点 1)指向 4。
1.初始化
申请一个节点方便后续操作。 2. p指向1 q指向2 3. tmp.next b; a.next b.next; 操作过程中不要丢失节点
现在节点的顺序是2 1 3 4 不好看那我转一下是不是清晰多了 一次调换两个节点 4. 接下来 temp和p q指向 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(headnull){return null;}ListNode prenew ListNode(-1);ListNode ppre;ListNode qpre;pre.nexthead;ListNode temppre;while(q!nullq.next!nullq.next.next!null){pp.next;qq.next.next;temp.nextq;p.nextq.next;q.nextp;tempp;qp;}return pre.next;}
}
运行结果
