【算法系列-链表】交换链表节点(反转 + 交换)
文章目录
- 【算法系列-链表】交换链表节点(反转 + 交换)
- 1. 反转链表
- 1.1 思路分析🎯
- 1.2 解题过程🎬
- 1.3 代码示例🌰
- 2. 两两交换链表中的节点
- 2.1 思路分析🎯
- 2.2 解题过程🎬
- 2.3 代码示例🌰
1. 反转链表
【题目链接】: LeetCode 206 反转链表
1.1 思路分析🎯
使用双指针即可解决这道问题，从head节点开始，让当前节点的下一个节点指向当前节点的上一个节点即可，最后记得将head节点的下一个节点指向null，因为此时的节点head已经是链表的最后一个节点了
提供图解如下：
1.2 解题过程🎬
初始化 慢指针 slow = head，快指针 fast = slow.next 当fast != null 时进入循环： 创建临时指针temp = fast.next，用来保存当前快指针的下一个节点；
之后让 fast指针的下一个节点指向 slow指针所指节点，随后slow指针指向fast指针所指节点，并让fast往后移动，即fast = temp，重复以上过程直到循环结束；
最后需要将head节点即最开始的头节点的下一个节点指向 NULL，否则会出现"闭环"，返回此时的slow节点即为反转后链表的头节点
1.3 代码示例🌰
class Solution {public ListNode reverseList(ListNode head) {if (head == null) {return head;}ListNode slow = head;ListNode fast = slow.next;while (fast != null) {ListNode temp = fast.next;fast.next = slow;slow = fast;fast = temp;}head.next = null;return slow;}
}
2. 两两交换链表中的节点
【题目链接】: LeetCode 24 两两交换链表中的节点
2.1 思路分析🎯
这道题通过模拟的方式解决，但最重要的是理清楚两个节点交换后此时的链表整体情况，将整个过程画出来更容易分析：
2.2 解题过程🎬
定义一个虚拟头节点vhead，同时定义一个cur节点指向vhead； 当 cur.next != null && cur.next.next != null 时，进入循环：
步骤1：定义节点 temp1：需要进行位置交换的两个节点之中的左侧节点；temp2：需要进行位置交换的两个节点之中的右侧节点的下一个节点；
步骤2：让 cur.next 指向 cur.next.next；
步骤3：经过步骤2 此时 的cur.next 已指向 需要进行位置交换的两个节点之中的右侧节点，此时在让这个右侧节点的下一个节点指向其需要交换位置的节点，即 cur.next.next = temp1;
步骤4：经过上述几个步骤节点已经交换好了位置，之后让temp.next 指向 temp2 即完成了链表完整的串联，最后让cur 指向 temp；
重复上述步骤直到循环结束，返回 vhead.next 即可
2.3 代码示例🌰
class Solution {public ListNode swapPairs(ListNode head) {ListNode vhead = new ListNode();vhead.next = head;ListNode cur = vhead;while (cur.next != null && cur.next.next != null) {ListNode temp1 = cur.next;ListNode temp2 = temp1.next.next;cur.next = cur.next.next;cur.next.next = temp1;temp1.next = temp2;cur = temp1;}return vhead.next;}
}
以上便是对链表节点交换类型题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨
