主要记录一些简单的算法和数据结构的题目，一方面是自己在准备的积累一方面适合复习使用。代码不一定最优，但是思考过程基本会给。
第二周，算法给生活加点料。
1.按照左一个右一个方式重新组合单链表
要求：例如：1->2->3->4->5->6,转变后为1->4->2->5->3->6
想法：首先想到的是可以先遍历一遍，得到长度len，然后知道了哪里是中点。然后呢就可以一个从头开始，一个从中间开始一次遍历然后插入后半部分的数据。这样的时间复杂度大致上为N，空间呢也只用了一个暂存用的额外空间。
public class Demo06 {
public class Node{
public int value;
public Node next;
public Node(int value){
this.value = value;
}
}
public void relocal(Node head){
//判空
if(head == null || head.next == null)
return;
Node mid = head;
Node right = head.next;
//要先找打中点的位置，所以令right行进步骤是mid的两倍
while(right.next != null && right.next.next != null){
mid = mid.next;
right = right.next.next;
}
right = mid.next;
mid.next = null;
margeLR(head,right);
}
//现在开始写合并寒素
public void margeLR(Node left,Node right){
Node next = null;
//交换算法
while(left.next != null){
next = right.next;
right.next = left.next;
left.next = right;
left = right.next;
right = next;
}
left.next = right;
}
}2.合并两个有序的单链表
要求：合并后的单链表依旧有序。
想法：既然已经有序了，哪我们一次遍历两个然后比较大小即可。但是呢我们再思考，是放入一个新的链表呢还是旧链表呢？答案肯定是不额外申请啦。然后呢我们就可以做了。一个为主链，一个为辅链。
public class Demo07 {
public class Node{
public int value;
public Node next;
public Node(int value){
this.value = value;
}
}
public Node merge(Node head1, Node head2){
//先判断是否为空,当其中一个为空时，直接返回另一个即可
if(head1 == null || head2 == null){
return head1 != head2 ? head1 : head2;
}
//选择一个主链表
Node head = head1.value < head2.value ? head1 : head2;
Node cur1 = head == head1 ? head1 : head2;
Node cur2 = head == head2 ? head2 : head1;
Node pre = null;
Node next = null;
while(cur1 != null && cur2 != null){
if(cur1.value <= cur2.value){
pre = cur1;
cur1 = cur1.next;
}else{
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
//最后判断以下那个时主链即可
pre.next = cur1 == null ? cur2 : cur1;
return head;
}
}3.向有序的环形链表中插入新节点
要求：时间复杂度为N，额外空间为1。
想法：对于有序的环形链表。我们要考虑插入的节点值对应的位置，如果说插入值小于头结点，那么要遍历一遍后找到了最大节点后插入，这个就类似于最大节点的插入。普通节点类似。
public class Demo08 {
public class Node{
public int value;
public Node next;
public Node(int value){
this.value = value;
}
}
public Node insertNewNode(Node head, int num){
Node node = new Node(num);
if(head == null){
//自己成环
node.next = node;
return node;
}
Node pre = head;
Node cur = head.next;
//查找对应的元素位置
while(cur != head){
if(pre.value <= num && cur.value >= num){
break;
}
pre = cur;
cur = cur.next;
}
//插入
pre.next = node;
node.next = cur;
return head.value < num ? head : node;
}
}4.单链表的选择排序
要求：没啥要求，额外空间为1即可。
想法：emmm没啥想法，那就按照选择排序做呗。每次遍历找到最小的放在该放的位置就行了。
public class Demo09 {
public class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
}
public Node selectionSort(Node head){
Node tail = null;
Node cur = head; // 未排序部分
Node samllPre = null;
Node samll = null;
while(cur != null){
samll = cur;
samllPre = getSamllPre(cur);
//取出对应当前最小的值
if(samllPre != null){
samll = samllPre.next;
samllPre.next = samll.next;
}
cur = cur == samll ? cur.next : cur;
//给尾部增加找到的最小的值
if(tail == null){
head = samll;
}else{
tail.next = samll;
}
tail = samll;
}
return head;
}
//遍历找出相对于的节点的前一个节点
public Node getSamllPre(Node head){
Node samllPre = null;
Node samll = head;
Node pre = head;
Node cur = head.next;
while(cur != null){
if(cur.value < samll.value){
samllPre = pre;
samll = cur;
}
pre = cur;
cur = cur.next;
}
return samllPre;
}
}
