题目地址
https://leetcode.com/problems/swap-nodes-in-pairs/description/
题目描述
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
思路
设置一个dummy 节点简化操作,dummy next 指向head。
- 初始化first为第一个节点
- 初始化second为第二个节点
- 初始化current为dummy
- first.next = second.next
- second.next = first
- current.next = second
- current 移动两格
- 重复
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)
关键点解析
-
链表这种数据结构的特点和使用
-
dummyHead简化操作
代码
- 语言支持:JS,Python3
/* * @lc app=leetcode id=24 lang=javascript * * [24] Swap Nodes in Pairs * * https://leetcode.com/problems/swap-nodes-in-pairs/description/ * * algorithms * Medium (43.33%) * Total Accepted: 287.2K * Total Submissions: 661.3K * Testcase Example: '[1,2,3,4]' * * Given a linked list, swap every two adjacent nodes and return its head. * * You may not modify the values in the list's nodes, only nodes itself may be * changed. * * * * Example: * * * Given 1->2->3->4, you should return the list as 2->1->4->3. * */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs = function(head) { const dummy = new ListNode(0); dummy.next = head; let current = dummy; while (current.next != null && current.next.next != null) { // 初始化双指针 const first = current.next; const second = current.next.next; // 更新双指针和current指针 first.next = second.next; second.next = first; current.next = second; // 更新指针 current = current.next.next; } return dummy.next; };
Python3 Code:
class Solution: def swapPairs(self, head: ListNode) -> ListNode: """ 用递归实现链表相邻互换: 第一个节点的next是第三、第四个节点交换的结果,第二个节点的next是第一个节点; 第三个节点的next是第五、第六个节点交换的结果,第四个节点的next是第三个节点; 以此类推 :param ListNode head :return ListNode """ # 如果为None或next为None,则直接返回 if not head or not head.next: return head _next = head.next head.next = self.swapPairs(_next.next) _next.next = head return _nextLeetCode题解求一根绳子被切两刀能组成一个三角形的概率。
如题题解:我们可以设绳长为1,设:- 其中两段长为x, y且x, y都>0- 故第三段长为1-x-y且>0故可以在二维坐标轴画出一个三角形(由x=0;y=0;1-x-y=0围成)要想构成三角形还要满足:- x+y > 1-x-y => x+y > 0.5- x+1-x-y > y => y < 0.5- y+1…
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。10个小球,随机分到12个盒子里,求恰好10个盒子都为空的概率。要求用程序模拟十万次,暴力求出该概率来自:字节跳动 算法工程师一面的第一题 (3月30日,60分钟,牛客网视频面)https://www.nowcoder.com/discuss/395924