1. 链表合并
1.1 两个链表节点相加后合并
思路：
- 遍历2个链表，如果其中一个链表为空，则默认使用0来相加，都为空stop
- 节点相加，进位使用一个flag记录
- 创建新链表3步法
- 最后如果flag为1，也要连接上
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
if(l1 == null && l2 == null){
return result;
}
ListNode cur = result;
int flag = 0;
while (l1 != null || l2!=null){
//如果某个链表为null，创建默认节点进行相加
l1 = l1 == null ? new ListNode(0) : l1;
l2 = l2 == null ? new ListNode(0) : l2;
int count = l1.val + l2.val + flag;
flag = count / 10;
count = count % 10;
ListNode node = new ListNode(count);
//创建新节点，并连接起来
if(result == null){
//1.头节点赋值
result = node;
}else{
//2.遍历指针连接到新节点
cur.next = node;
}
//3.遍历指针指向最新的节点
cur = node;
l1 = l1.next;
l2 = l2.next;
}
if(flag == 1){
cur.next = new ListNode(flag);
}
return result;
}
1.2. 两个有序链表合并
思路：
- 遍历2个链表，如果其中一个链表为空，创建默认最大节点，都为空stop
- 谁小谁移动
- 创建新链表3步法
public ListNode sortedListMerge(ListNode l1, ListNode l2) {
ListNode result = null;
if(l1 == null && l2 == null){
return result;
}
ListNode cur = result;
if(l1!=null || l2!=null){
//如果某个链表为null，创建默认节点（最大整数）
l1 = l1 == null ? new ListNode(Integer.MAX_VALUE) : l1;
l2 = l2 == null ? new ListNode(Integer.MAX_VALUE) : l2;
int min;
//谁小谁移动
if(l1.val <= l2.val){
min = l1.val;
//l1移动
l1 = l1.next;
}else {
min = l2.val;
//l2移动
l2 = l2.next;
}
ListNode node = new ListNode(min);
//创建新节点，并连接起来
if(result == null){
//1.头节点赋值
result = node;
}else{
//2.遍历指针连接到新节点
cur.next = node;
}
//3.遍历指针指向最新的节点
cur = node;
}
return result;
}
1.3 合并K个有序链表
思路：
- 遍历，所有数据建立小顶堆
- poll
- 创建新链表3步法
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
if(lists.length == 1){
return lists[0];
}
PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
//建立小顶堆
for (int i = 0; i < lists.length; i++) {
ListNode cur = lists[i];
while (cur!=null){
queue.add(cur);
cur = cur.next;
}
}
//遍历
ListNode result = null;
ListNode cur = result;
while (!queue.isEmpty()){
ListNode poll = queue.poll();
ListNode node = new ListNode(poll.val);
if(result == null){
result = node;
}else{
cur.next = node;
}
cur = node;
}
return result;
}
2. 链表回文
2.1 判断链表是否回文
思路：
- 快慢指针确定链表中点位置
- 从slow的下一个节点开始，逆转链表，逆转3指针兄弟上场
- 逆转完的链表头为copy，记得中点的slow指针的next断开，不然成环了
- 从链表头尾开始遍历，如果发现不同节点，直接返回false，直到遍历到中点位置
- 返回结果前，记得把链表恢复，还是使用逆转链表的方法（见基础篇2.7）
public boolean isPalindrome(ListNode head) {
if(head == null){
return false;
}
if(head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head;
while (slow.next !=null && fast.next != null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
//此时slow在第（n+1）/2的位置上，中点位置
//从slow的下一个节点开始，逆转链表，逆转3指针兄弟上场，逆转完的链表头为copy，
ListNode pre = slow;
ListNode cur = slow.next;
ListNode copy = slow;
while(cur!=null){
pre = copy;
copy = cur;
cur = cur.next;
copy.next = pre;
}
//slow的next断开，不然成环了
slow.next = null;
//从链表头尾开始遍历，如果发现不同节点，直接返回false，直到遍历到中点位置
cur = head;
pre = copy;
boolean resultFlag = true;
while(cur!=null && pre!=null){
if(cur.val != pre.val){
return false;
}
cur = cur.next;
pre = pre.next;
}
//恢复链表，从链表尾部copy开始，重新逆转链表
pre = null;
cur = copy;
copy = null;
while(cur!=null){
pre = copy;
copy = cur;
cur = cur.next;
copy.next = pre;
}
return resultFlag;
}
3. 随机链表的复制
思路：
1.遍历节点，克隆节点放在当前节点的后面，1 1' 2 2' 3 3'
2.复制后隔2个节点这样取，取到1，2，3，设置copy节点的random节点
3.split，将copy节点从链表上分离
public Node copyRandomList(Node head) {
if(head == null){
return head;
}
Node cur = head;
Node a = null;
//遍历节点，克隆节点放在当前节点的后面，1 1' 2 2' 3 3'
while (cur != null){
a = cur.next;
cur.next = new Node(cur.val);
cur.next.next = a;
cur = a;
}
cur = head;
Node b = null;
//2个2个取，设置copy节点的random节点
while(cur!=null){
a = cur.next.next;
b = cur.next;
b.random = cur.random!=null ? cur.random.next : null;
cur = a;
}
//split，将copy节点从链表上分离
Node result = head.next;
cur = head;
while(cur!=null){
a = cur.next.next;
b = cur.next;
cur.next = a;
b.next = a!=null ? a.next : null;
cur = a;
}
return result;
}
4. Josephu问题
描述：约瑟夫问题，已知n个人（编号1，2....n）坐在圆桌上，从编号k的位置开始报数，报到m时，这个人出列，他的下个人又从1开始报，报到m出列，重复这个动作，直到圆桌上的人全部出列。求出列的顺序。
思路：
- 建立一个具有n个节点的单向循环链表
- 确定第一个报数的位置
- 不断的从链表中删除一个节点，直至链表为空
public static List<Integer> josephus(int n, int k, int m){
List<Integer> result = new ArrayList<>();
//建立链表
ListNode head = null;
ListNode cur = head;
for (int i = 1; i <=n ; i++) {
ListNode node = new ListNode(i);
if(head == null){
head = node;
}else{
cur.next = node;
}
cur = node;
}
//首位连接成单向循环链表
cur.next = head;
//确定第一个报数的位置
cur = head;
for (int j = 0; j < k-1; j++) {
head = head.next;
cur = head;
}
//此时，head和cur同时到达第一个报数的位置
while(cur != null){
//找到报数m，出列的位置
for (int i = 0; i < m-1; i++) {
cur = cur.next;
}
result.add(cur.val);
//出列
head.next = cur.next;
cur.next = null;
cur = head.next;
head = cur;
}
return result;
}
