一、 快慢指针

1)输入链表头节点,奇数长度返回中点,偶数长度返回上中点 
2)输入链表头节点,奇数长度返回中点,偶数长度返回下中点 
3)输入链表头节点,奇数长度返回中点前一个,偶数长度返回上中点前一个 
4)输入链表头节点,奇数长度返回中点前一个,偶数长度返回下中点前一个

快慢指针只是大体的结构，不同的题目还需要不同的细节

public class Code01_LinkedListMid {
	public static class Node {
		public int value;
		public Node next;

		public Node(int v) {
			value = v;
		}
	}

	// head 头
	public static Node midOrUpMidNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return head;
		}
		// 链表有3个点或以上
		Node slow = head.next;
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrDownMidNode(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node slow = head.next;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrUpMidPreNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node slow = head;
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static Node midOrDownMidPreNode(Node head) {
		if (head == null || head.next == null) {
			return null;
		}
		if (head.next.next == null) {
			return head;
		}
		Node slow = head;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
}

二、 小中大

将单向链表按某值划分成左边小、中间相等、右边大的形式 
1)把链表放入数组里,在数组上做 partition(笔试用) 
2)分成小、中、大三部分,再把各个部分之间串起来(面试用)

解法一：利用数组partition

    public static Node listPartition1(Node head, int pivot) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        int i = 0;
        while (cur != null) {
            i++;
            cur = cur.next;
        }
        Node[] nodeArr = new Node[i];
        i = 0;
        cur = head;
        for (i = 0; i != nodeArr.length; i++) {
            nodeArr[i] = cur;
            cur = cur.next;
        }
        arrPartition(nodeArr, pivot);
        for (i = 1; i != nodeArr.length; i++) {
            nodeArr[i - 1].next = nodeArr[i];
        }
        nodeArr[i - 1].next = null;
        return nodeArr[0];
    }

    public static void arrPartition(Node[] nodeArr, int pivot) {
        int small = -1;
        int big = nodeArr.length;
        int index = 0;
        while (index != big) {
            if (nodeArr[index].value < pivot) {
                swap(nodeArr, ++small, index++);
            } else if (nodeArr[index].value == pivot) {
                index++;
            } else {
                swap(nodeArr, --big, index);
            }
        }
    }

    public static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }

解法二：将链表分为小中大三部分，再把各部分的头结点和尾节点连在一起

    public static Node listPartition2(Node head, int pivot) {
        Node sH = null; // small head
        Node sT = null; // small tail
        Node eH = null; // equal head
        Node eT = null; // equal tail
        Node bH = null; // big head
        Node bT = null; // big tail
        Node next = null; // save next node
        // every node distributed to three lists
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sH == null) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }
            } else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (bH == null) {
                    bH = head;
                    bT = head;
                } else {
                    bT.next = head;
                    bT = head;
                }
            }
            head = next;
        }
        // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
        if (sT != null) { // 如果有小于区域
            sT.next = eH;
            eT = eT == null ? sT : eT; // 下一步，谁去连大于区域的头，谁就变成eT
        }
        // 上面的if，不管跑了没有，et
        // all reconnect
        if (eT != null) { // 如果小于区域和等于区域，不是都没有
            eT.next = bH;
        }
        return sH != null ? sH : (eH != null ? eH : bH);
    }

问题三：判断链表的节点是否回文

• 解法一：需要空间为n的栈

	// need n extra space
	public static boolean isPalindrome1(Node head) {
		Stack<Node> stack = new Stack<>();
		Node cur = head;
		while (cur != null) {
			stack.push(cur);
			cur = cur.next;
		}
		while (head != null) {
			if (head.value != stack.pop().value) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

• 解法二：需要空间为n/2的栈

    // need n/2 extra space
    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node right = head.next;
        Node cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        Stack<Node> stack = new Stack<Node>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

• 解法三：额外空间为O(1)

    // need O(1) extra space
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        //找到中点
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) { // find mid node
            n1 = n1.next; // n1 -> mid
            n2 = n2.next.next; // n2 -> end
        }
        // 逆转右半部分
        Node pre = n1;//中点
        Node r_head = pre.next;//右半部分的第一个节点
        pre.next = null; // mid.next -> null
        Node next = null;
        while (r_head != null) { // right part convert
            next = r_head.next; // n3 -> save next node
            r_head.next = pre; // next of right node convert
            pre = r_head; // n1 move
            r_head = next; // r_head move
        }

        //判断左右部分是否相同
        r_head = pre; //已经逆转的右半部分的头结点
        Node l_head = head;//左半部分的头结点
        boolean res = true;
        while (r_head != null && l_head != null) { // check palindrome
            if (r_head.value != l_head.value) {
                res = false;
                break;
            }
            r_head = r_head.next;
            l_head = l_head.next;
        }

        //恢复链表原来的样子
        r_head = pre;
        next = null;
        pre = null;
        while (r_head != null) { // recover list
            next = r_head.next;
            r_head.next = pre;
            pre = r_head;
            r_head = next;
        }
        return res;
    }

问题四：复制新链表

一种特殊的单链表节点类描述如下
class Node{ 
	int value;
	Node next; 
	Node rand; 
	Node(int val){ 
		value = val;
	}
}
rand指针是单链表节点结构中新增的指针,rand可能指向链表中的任意一个节点,也可能指向nul。 
给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个函数完成这个链表的复制,并返回复制的新链表的头节点。 
【要求】 时间复杂度O(N).额外空间复杂度O(1)

• 解法一：使用哈希表实现

	public static Node copyListWithRand1(Node head) {
		HashMap<Node, Node> map = new HashMap<>();
		Node cur = head;
		while (cur != null) {
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}
		cur = head;
		while (cur != null) {
			// cur 老
			// map.get(cur) 新
			map.get(cur).next = map.get(cur.next);
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		return map.get(head);
	}

• 解法二：在本链表中实现

	public static Node copyListWithRand2(Node head) {
		if (head == null) {
			return null;
		}
		Node cur = head;
		Node next = null;
		// copy node and link to every node
		// 1 -> 2
		// 1 -> 1' -> 2 -> 2'
		while (cur != null) {
			// cur 老   next 老的下一个
			next = cur.next;
			cur.next = new Node(cur.value);
			cur.next.next = next;
			cur = next;
		}
		cur = head;
		Node curCopy = null;
		// set copy node rand
		// 1 -> 1' -> 2 -> 2'
		while (cur != null) {
			// cur 老
			// cur.next  新 copy
			next = cur.next.next;
			curCopy = cur.next;
			curCopy.rand = cur.rand != null ? cur.rand.next : null;
			cur = next;
		}
		// head  head.next
		Node res = head.next;
		cur = head;
		// split
		while (cur != null) {
			next = cur.next.next;
			curCopy = cur.next;
			cur.next = next;
			curCopy.next = next != null ? next.next : null;
			cur = next;
		}
		return res;
	}

问题五：找到两条链表的第一个交点

给定两个可能有环也可能无环的单链表,头节点head1和head2 
请实现一个函数,如果两个链表相交,请返回相交的第一个节点。 
如果不相交,返回null 
【要求】如果两个链表长度之和为N,时间复杂度请达到O(N),额外空间复杂度请达到O(1)。

• 1.若两条链表相交，则它们必定都有环或者都没有环

• 2.若两条无环的链表相交，则它们后部分的链必定重叠，且有相同的尾节点

• 3.两条有环的链表有三种情况

  • 1. 两条链表不相交
  • 2. 两条链表相交在同一个节点
  • 3. 两条链表相交在不同节点，这两个节点都可以被认为是相交的第一个节点

	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	//方法入口
	public static Node getIntersectNode(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		//两条链表无环
		if (loop1 == null && loop2 == null) {
			return noLoop(head1, head2);
		}
		//两条链表有环
		if (loop1 != null && loop2 != null) {
			return bothLoop(head1, loop1, head2, loop2);
		}
		//两条链表一个有环一个无环，无交点
		return null;
	}

	// 找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		// n1 慢  n2 快
		Node n1 = head.next; // n1 -> slow
		Node n2 = head.next.next; // n2 -> fast
		while (n1 != n2) {
			if (n2.next == null || n2.next.next == null) {
				return null;
			}
			n2 = n2.next.next;
			n1 = n1.next;
		}
		n2 = head; // n2 -> walk again from head
		while (n1 != n2) {
			n1 = n1.next;
			n2 = n2.next;
		}
		return n1;
	}

	// 如果两个链表都无环，返回第一个相交节点，如果不相交，返回null
	//如果两条链表有相同的尾节点，则相交；否则，不相交。
	public static 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;
		}
		// n  :  链表1长度减去链表2长度的值
		cur1 = n > 0 ? head1 : head2; // 谁长，谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
		n = Math.abs(n);
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

	// 两个有环链表，返回第一个相交节点，如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if (loop1 == loop2) {
			//相交在同一点
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			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;
		} else {
			//相交在不同点或者不相交
			//若loop1一直next回到loop1没有遇到loop2，则没有相交
			cur1 = loop1.next;
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

问题六：在不给出头结点的情况下删除给定的节点

• 解法一：借尸还魂

将该节点的下一个节点的value贴到该节点，然后跳过该节点的下一个节点

缺点：没有完全删除，只是将value覆盖了，有些情况可能不能覆盖

• 解法二：（有错误）

	Node a = new Node(1);
	Node b = new Node(2);
	Node c = new Node(3);
	
	a.next = b;
	b.next = c;
	
	c = null;

若直接将c设为null，不会改变堆内存中链表的结构，b依然指向c，改变的只是c不再指向Node（3）了