合并链表
package 复现代码;
import java.util.ArrayList;
/**
* @Classname 链表的合并
* @Description TODO
* @Date 2020/12/22 15:29
* @Created by xjl
*/
public class 链表的合并 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
/**
* @description TODO 合并链表
* @param: lists
* @date: 2020/12/22 15:30
* @return: 复现代码.链表的合并.ListNode
* @author: xjl
*/
public ListNode merge(ArrayList lists) {
if (lists.size() == 0) {
return null;
}
ListNode res = lists.get(0);
for (int i = 1; i < lists.size(); i++) {
res = mergeTwoLists(lists.get(i), res);
}
return res;
}
private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
ListNode curr1 = head1;
ListNode curr2 = head2;
ListNode res = new ListNode(0);
ListNode dumpy=res;
while (curr1 != null && curr2 != null) {
if (curr1.val > curr2.val) {
dumpy.next = curr2;
curr2 = curr2.next;
} else {
dumpy.next = curr1;
curr1 = curr1.next;
}
dumpy = dumpy.next;
}
if (curr1 != null) {
dumpy.next = curr1;
}
if (curr2 != null) {
dumpy.next = curr2;
}
return res.next;
}
}
public ListNode mergeKLists(ArrayList lists) {
if (lists.size() == 0) return null;
ListNode res = lists.get(0);
for (int i = 1; i < lists.size(); i++) {
res = mergeTwoLists(lists.get(i), res);
}
return res;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个新的链表
ListNode pre = new ListNode(0);
ListNode cur = pre;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 任一为空,直接连接另一条链表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return pre.next;
}
}
链表的指定区间翻转
package 复现代码;
/**
* @Classname 链表的指定翻转
* @Description TODO
* @Date 2020/12/22 15:49
* @Created by xjl
*/
public class 链表的指定翻转 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
/**
* @description TODO 第一步是就是的找到的是m-1的位置 然后利用的是的翻转链表的第二种的方式来实现这样样的执行就是的是n-m次就结束
* @param: head
* @param: m
* @param: n
* @date: 2020/12/22 15:51
* @return: 复现代码.链表的指定翻转.ListNode
* @author: xjl
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return head;
}
ListNode dumpy = new ListNode(0);
dumpy.next = head;
ListNode pre = dumpy;//第一段最后的一个节点
//找到第m个节点
for (int i = 1; i < m; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = m; i < n; i++) {
ListNode future = cur.next;
cur.next = future.next;
future.next = pre.next;
pre.next = future;
}
return dumpy.next;
}
}
无序单链表的排序
package 复现代码;
/**
* @Classname 无序单链表的排序
* @Description TODO
* @Date 2020/12/22 17:34
* @Created by xjl
*/
public class 无序单链表的排序 {
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
/**
* @description TODO 分割链表采用的快慢指针 第二是合并链表
* @param: head
* @date: 2020/12/22 17:36
* @return: void
* @author: xjl
*/
public ListNode sortInList(ListNode head) {
// write code here
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next;//一定要设置的head的下一个
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode second = slow.next;
slow.next = null;
ListNode head1 = sortInList(head);
ListNode head2 = sortInList(second);
ListNode ans = merge(head1, head2);
return ans;
}
/**
* @description TODO 合并链表
* @param: head1
* @param: head2
* @date: 2020/12/22 18:13
* @return: 复现代码.无序单链表的排序.ListNode
* @author: xjl
*/
public ListNode merge(ListNode head1, ListNode head2) {
ListNode curr1 = head1;
ListNode curr2 = head2;
ListNode res = new ListNode(0);
ListNode dumpy = res;
while (curr1 != null && curr2 != null) {
if (curr1.val > curr2.val) {
dumpy.next = curr2;
curr2 = curr2.next;
} else {
dumpy.next = curr1;
curr1 = curr1.next;
}
dumpy = dumpy.next;
}
if (curr1 != null) {
dumpy.next = curr1;
}
if (curr2 != null) {
dumpy.next = curr2;
}
return res.next;
}
}
约瑟夫问题
package 复现代码;
import java.util.ArrayList;
/**
* @Classname 环形链表的约瑟夫问题
* @Description TODO
* @Date 2020/12/22 18:40
* @Created by xjl
*/
public class 环形链表的约瑟夫问题 {
/**
* @description TODO 约瑟夫问题
* @param: n
* @param: m
* @date: 2020/12/22 18:50
* @return: int
* @author: xjl
*/
public int ysf(int n, int m) {
//1 通过的链表
if (n == 0 || m == 0) {
return -1;
}
ArrayList list = new ArrayList();
for (int i = 0; i < n; i++) {
list.add(i);
}
int removeIndex = 0;
while (list.size() != 1) {
removeIndex = (removeIndex + m - 1) % list.size();
list.remove(removeIndex);
}
return list.get(0);
}
/**
* @description TODO f(n,m)=(f(n-1,m)+m)%n
* @param: n
* @param: m
* @date: 2020/12/22 18:55
* @return: int
* @author: xjl
*/
public int ysf1(int n, int m) {
//通过的数学公式
if (n == 0 || m == 0) {
return -1;
}
int last = 0;
for (int i = 2; i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?