[算法]链表题目
两两交换链表中的节点
题目描述
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
先提供一个投机取巧的办法,既然转换链表中的前后关系比较麻烦,那我不妨反其道而行之,我直接交换链表的值,让链表的关系保持不变即可。
还有一种思路是通过递归来计算。
代码
解法1:
/** * Definition for singly-linked list. * class ListNode(var _x: Int = 0) { * var next: ListNode = null * var x: Int = _x * } */ object Solution { def swapPairs(head: ListNode): ListNode = { var newHead = head while(newHead != null && newHead.next != null){ val temp = newHead.x newHead.x = newHead.next.x newHead.next.x = temp newHead = newHead.next.next } head } }
解法2:
class Solution { public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; } }
反转链表II
题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
同上,投机取巧的办法只需要交换值即可,用一个栈来临时存储数据。
也可以参考之前反转链表的思路,将链表分成三段,m之前的,m到n的,n之后的。
代码
解法1(扫描了2次,不太符合要求):
/** * Definition for singly-linked list. * class ListNode(var _x: Int = 0) { * var next: ListNode = null * var x: Int = _x * } */ import java.util.Stack object Solution { def reverseBetween(head: ListNode, m: Int, n: Int): ListNode = { var newHead = head var index = 1 val stack: Stack[Int] = new Stack[Int]() while(newHead != null){ if(index >= m && index <= n){ stack.push(newHead.x) } newHead = newHead.next index += 1 } newHead = head index = 1 while(newHead != null){ if(index >= m && index <= n){ newHead.x = stack.pop() } newHead = newHead.next index += 1 } head } }
解法2:
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode cur = head, pre = dummy; int i = 1; while (i < m) {//通过i去寻找开始反转的地方 pre = cur; cur = cur.next; i++; } ListNode node = pre;//node记录的是反转链表的前一个节点 //反转从m到n的链表,解法同206题 while (i <= n) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; i++; } //反转链表接回原链表 node.next.next = cur; node.next = pre; return dummy.next; } }
解释下子链表怎么接回原链表:
1->2->3->4->5->null, m = 2, n = 4,
子链表反转完成后是这样的
1<->2<-3<-4 5->null,此时cur = 5, pre = 4, node = 1,接下来就显而易见了。
https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode/
相关文章
- 散列技术之链地址法(基于无序链表)
- 【算法】【链表模块】二叉树空间复杂度为O(1)的遍历方法(Morris算法)
- 【算法】【链表模块】使用单链表进行选择排序
- 【算法】【链表模块】单链表删除指定值节点
- 【算法】【链表模块】单链表每k个节点之间逆序
- 【算法】【链表模块】两个单链表寻找交点
- 【算法】【链表模块】给定整数num,将链表调整为左边小于num,右边大于num,中间等于num
- 【算法】【链表模块】单链表解决约瑟夫问题
- 单向链表的反转
- 【BZOJ3502/2288】PA2012 Tanie linie/【POJ Challenge】生日礼物 堆+链表(模拟费用流)
- 链表算法letcode
- [算法]头条面试—奇数位升序偶数位降序链表排序
- 【创】数据结构与算法————链表byC语言【C语言网】
- 剑指offer解法汇总76-删除链表中重复的结点
- 剑指offer编程题解法汇总52-两个链表的第一个公共结点
- 面试题 02.05. 链表求和
- 【Java数据结构与算法】LeetCode 0019. 删除链表的倒数第N个结点
- 【Java数据结构与算法】LeetCode 0024.两两交换链表中的节点
- LeetCode | 一探环形链表的奥秘【快慢双指针妙解BAT等大厂经典算法题】
- 剑指Offer习题整理-链表笔记
- 【算法刷题】链表题型及方法归纳
- 【链表OJ题(三)】链表中倒数第k个结点
- 5链表的应用--学生管理系统
- C# 算法之链表、双向链表以及正向反向遍历实现
- leetcode算法237.删除链表中的节点
- leetcode算法206.反转链表