package com.xiaodai.algorithm;

public class LinkedListUtil {

/**

public static class Node {

public int value;

public Node next;

public Node(int data) {

value = data;

}

}

/**

public static class DoubleNode {

public int value;

public DoubleNode last;

public DoubleNode next;

public DoubleNode(int data) {

value = data;

}

}

/**

public boolean hasCycle(Node head) {

if (head == null || head.next == null) {

return false;

}

Node slow = head;

Node fast = head.next;

while (slow != fast) {

if (fast == null || fast.next == null) {

return false;

}

slow = slow.next;

fast = fast.next.next;

}

// 有环的话一定追的上，但不一定是第一次成环的节点

return true;

}

/**

public static Node reverseLinkedList(Node head) {

Node pre = null;

Node next = null;

while (head != null) {

next = head.next;

head.next = pre;

pre = head;

head = next;

}

return pre;

}

/**

public static Node removeValue(Node head, int num) {

// 从链表的头开始，舍弃掉开头的且连续的等于num的节点

while (head != null) {

if (head.value != num) {

break;

}

head = head.next;

}

// head来到 第一个不需要删的位置

Node pre = head;

Node cur = head;

// 快慢指针

while (cur != null) {

if (cur.value == num) { // 快指针cur向下滑动，如果值等于num，则暂时把下一个节点给慢指针的下一个指向。从而跳过等于num的节点

pre.next = cur.next;

} else { // cur此时到了不等于num的节点，则慢指针追赶上去。达到的效果就是等于num的节点都被删掉了

pre = cur;

}

// 快指针向下滑动

cur = cur.next;

}

return head;

}

/**

public void printCommonPart(Node head1, Node head2) {

System.out.println("Common Part: ");

while (head1 != null && head2 != null) {

if (head1.value < head2.value) {

head1 = head1.next;

} else if (head1.value > head2.value) {

head2 = head2.next;

} else {

System.out.println(head1.value);

head1 = head1.next;

head2 = head2.next;

}

}

System.out.println();

}

/**

public Node removeLastKthNode(Node head, int lastKth) {

if (head == null || lastKth < 1) {

return head;

}

// cur指针也指向链表头节点

Node cur = head;

// 检查倒数第lastKth个节点的合法性

while (cur != null) {

lastKth--;

cur = cur.next;

}

// 需要删除的是头结点

if (lastKth == 0) {

head = head.next;

}

if (lastKth < 0) {

// cur回到头结点

cur = head;

while (++lastKth != 0) {

cur = cur.next;

}

// 次吃cur就是要删除的前一个节点。把原cur.next删除

cur.next = cur.next.next;

}

// lastKth > 0的情况，表示倒数第lastKth节点比原链表程度要大，即不存在

return head;

}

/**

public Node removeMidNode(Node head) {

// 无节点，或者只有一个节点的情况，直接返回

if (head == null || head.next == null) {

return head;

}

// 链表两个节点，删除第一个节点

if (head.next.next == null) {

return head.next;

}

Node pre = head;

Node cur = head.next.next;

// 快慢指针

if (cur.next != null && cur.next.next != null) {

pre = pre.next;

cur = cur.next.next;

}

// 快指针走到尽头，慢指针奇数长度停留在中点，偶数长度停留在上中点。删除该节点

pre.next = pre.next.next;

return head;

}

/**

public Node getLoopNode(Node head) {

// 节点数目不足以成环，返回不存在成环节点

if (head == null || head.next == null || head.next.next == null) {

return null;

}

Node n1 = head.next; // slow指针

Node n2 = head.next.next; // fast指针

while (n1 != n2) {

// 快指针提前到达终点，该链表无环

if (n2.next == null || n2.next.next == null) {

return null;

}

n2 = n2.next.next;

n1 = n1.next;

}

// 确定成环，n2回到头节点

n2 = head;

while (n1 != n2) {

n2 = n2.next;

n1 = n1.next;

}

// 再次相遇节点，就是成环节点

return n1;

}

/**

public Node noLoop(Node head1, Node head2) {

if (head1 == null || head2 == null) {

return null;

}

Node cur1 = head1;

Node cur2 = head2;

int n = 0;

while (cur1.next != null) {

n++;

cur1 = cur1.next;

}

while (cur2.next != null) {

n--;

cur2 = cur2.next;

}

// 最终没汇聚，说明两个链表不相交

if(cur1 != cur2) {

return null;

}

cur1 = n > 0 ? cur1 : cur2;

cur2 = cur1 == head1 ? head2 : head1;

n = Math.abs(n);

while (n != 0) {

n--;

cur1 = cur1.next;

}

while (cur1 != cur2) {

cur1 = cur1.next;

cur2 = cur2.next;

}

return cur1;

}

/**

public Node mergeTwoList(Node head1, Node head2) {

// base case

if (head1 == null || head2 == null) {

return head1 == null ? head2 : head1;

}

// 选出两个链表较小的头作为整个合并后的头结点

Node head = head1.value <= head2.value ? head1 : head2;

// 链表1的准备合并的节点，就是头结点的下一个节点

Node cur1 = head.next;

// 链表2的准备合并的节点，就是另一个链表的头结点

Node cur2 = head == head1 ? head2 : head1;

// 最终要返回的头结点，预存为head，使用引用拷贝的pre向下移动

Node pre = head;

while (cur1 != null && cur2 != null) {

if (cur1.value <= cur2.value) {

pre.next = cur1;

// 向下滑动

cur1 = cur1.next;

} else {

pre.next = cur2;

// 向下滑动

cur2 = cur2.next;

}

// pre向下滑动

pre = pre.next;

}

// 有一个链表耗尽了，没耗尽的链表直接拼上

pre.next = cur1 != null ? cur1 : cur2;

return head;

}

}