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

算法刷题记录6 - 反转链表和链表两两交换

news 来源：原创 2024/5/13 5:24:27

哎，都两周没刷题了，罪过

第一题

2023.10.29 周日
上链接
206. 反转链表
难度：简单
代码随想录文档
代码随想录视频
这道题说难不难，但是也不知道是太久没写没感觉了还是确实细节多，不看视频确实感觉不出写的问题在哪。。最大的问题是，我忘了单向链表的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 reverseList(ListNode head) {// 双指针法// 思路是 原地调换链表指针指向ListNode left = null; // 为什么是null呢？因为反转以后尾结点后面指向的是nullListNode right = head;ListNode tmp = null;// 从头结点朝着尾结点去反转指针方向while (right != null) { // 边界值怎么判断呢？当left为原来的尾结点的时候，right应该为null，不用再次指向left了，也就是可以不用再循环了tmp = right.next; // 为什么要保存这个呢？因为当右节点的next指向左节点的时候，原来right到原来right.next的链断了，找不到right.next了，循环进行不了了，所以提前保存。right.next = left;left = right; // 这个也要在right右移之前，调换顺序就不对了right = tmp; // 等于tmp，因为此时的right.next已经是left了}return left; // 循环结束，right为空，left为原来的尾结点也是反转后新表的头结点}
}

递归法

/*** 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 reverseList(ListNode head) {// 递归法return reverse(null, head); // 初始值}private ListNode reverse(ListNode left, ListNode right) {if(right == null) return left; // 递归出口，right为空则不需要再用right指向leftListNode tmp = right.next; // 保存下一个节点right.next = left; // 指针反向// left right 右移// left = right;// right = tmp;return reverse(right, tmp); // 自调用，值为原来更新的位置}
}

时空复杂度：On、O1

第二题

2023.10.29 周日
上链接
24. 两两交换链表中的节点
难度：中等
代码随想录文档
代码随想录视频
这道题和上一道有非常的类似，都是链表节点指针变换，区别在于边界值判断和怎么改变指针。
过程（黑色是原先的指针，红色是处理后的指针）
在这里插入图片描述
理解了这个图，就能理解这个题怎么做。
然后为什么要保存这么多节点呢？还和上一题一样。以上面这个图为例，
cur指向2，那么cur指向1的指针就断了，2可找不到1，所以提前firstnode记下；
继续，2要指向1，那么2到3就断了，3是下一个操作区间的起点，所以也要提前记下叫temp；
有一说一，这样其实不用secondnode了，因为这已知的。

第二题还有操作，连temp也不用留，比如说1已经记到firstnode，cur指到2的时候，此时1的next指向3，2的next指向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;ListNode dummy = new ListNode(-1); // 虚拟头结点dummy.next = head;ListNode cur = dummy;ListNode temp; // 临时节点，保存两个节点后面的节点ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点while (cur.next != null && cur.next.next != null) { // cur开始是dummy，不会为空，奇数节点时，偶数节点时temp = cur.next.next.next;firstnode = cur.next;secondnode = cur.next.next;cur.next = secondnode;       // 步骤一secondnode.next = firstnode; // 步骤二firstnode.next = temp;      // 步骤三cur = firstnode; // cur移动，准备下一轮交换}return dummy.next;}
}