单链表

单链表一些相关的算法集锦，单链表的算法可以提高逻辑能力。

反转链表

最基本的链表的题目，很简单的迭代操作，需要注意的就是保证时刻不要丢失Node，不要出现loop。

 /**
     * 链表反转，链表翻转
     * @param root
     * @return
     */
    private SingleNode reverseNode(SingleNode root) {
        if (root == null || root.next == null) {
            return root;
        }
        SingleNode result = root;
        SingleNode next = root.next;
        root.next = null;
        while (next != null) {
            SingleNode temp = next;
            next = next.next;
            temp.next = result;
            result = temp;
        }
        return result;
    }

移除链表中的元素

/**
     * 移除链表中的元素 普通写法，需要先找到不是val的head
     *
     * @param head
     * @param val
     * @return
     */
    public SingleNode removeElements(SingleNode head, int val) {
        if (head == null) {
            return head;
        }
        while (head.val == val) {
            head = head.next;
            if (head == null) {
                return head;
            }
        }
        SingleNode node = head;

        while (node.next != null) {
            if (node.next.val == val) {
                SingleNode temp = node.next.next;
                node.next = temp;
            }
            if (node.next == null) {
                break;
            }
            if (node.next.val != val) {
                node = node.next;
            }
        }
        return head;
    }

    /**
     * 移除链表中的元素，优化写法，使用一个头指针指向head，不用担心head就是需要移除的元素
     *
     * @param head
     * @param val
     * @return
     */
    public SingleNode removeElements2(SingleNode head, int val) {
        SingleNode preHead = new SingleNode(val - 1);
        preHead.next = head;
        SingleNode node = preHead;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            }
            if (node.next == null) {
                break;
            }
            if (node.next.val != val) {
                node = node.next;
            }
        }
        return preHead.next;
    }

合并两个顺序链表

 //合并两个顺序链表，方式1：左右为null的时候继续往后遍历
    public SingleNode merge(SingleNode left, SingleNode right) {
        if (left == null) return right;
        if (right == null) return left;
        SingleNode newNode = null;
        while (left != null || right != null) {
            if (left == null) {
                SingleNode n = right;
                right = right.next;
                n.next = newNode;
                newNode = n;
                continue;
            }
            if (right == null) {
                SingleNode n = left;
                left = left.next;
                n.next = newNode;
                newNode = n;
                continue;
            }
            if (left.val > right.val) {
                SingleNode n = right;
                right = right.next;
                n.next = newNode;
                newNode = n;
            } else {
                SingleNode n = left;
                left = left.next;
                n.next = newNode;
                newNode = n;
            }
        }
        return newNode;
    }

    //添加一个preHead指针，不在乎head是否为空
    public SingleNode mergeTwoLists(SingleNode l1, SingleNode l2) {
        SingleNode preHead = new SingleNode(0);
        SingleNode node = preHead;

        while (l1 != null || l2 != null) {
            if (l1 == null||l2 == null) {
                node.next = (l1==null)?l2:l1;
                break;
            }
            if (l1.val > l2.val) {
                SingleNode temp = l2;
                l2 = l2.next;
                node.next = temp;
                temp.next = null;
                node = temp;
            } else {
                SingleNode temp = l1;
                l1 = l1.next;
                node.next = temp;
                temp.next = null;
                node = temp;
            }
        }
        return preHead.next;
    }