关于链表经典算法题都在这里了

1.单链表反转（LeetCode 206）

//非递归解法
public ListNode reverseList(ListNode head) {
    //长度为0或1直接返回
    if (head == null || head.next == null) {
        return head;
    }
    ListNode currNode = head;
    ListNode preNode = null;
    //临时变量存储下一个
    ListNode nextTemp = null;
    while (currNode != null) {
        nextTemp = currNode.next;
        currNode.next = preNode;
        preNode = currNode;
        currNode = nextTemp;
    }
    return preNode;
}

2.链表中环的检测 (LeetCode 141)

//典型的快慢指针的思想。
//除此之外，当换不是无限大的时候我们也可以用死循环来判断有没有环，循环一段时间，看看next是不是为null.
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head;

    while (slow != null && fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            return true;
        }
    }
    return false;
}

3.求链表中环开始结点 (LeetCode 142)
解题思路：
1.首先通过快慢指针的方法判断链表是否有环；
2.接下来如果有环，则寻找入环的第一个节点。具体的方法为，首先假定链表起点到入环的第一个节点A的长度为a【未知】，到快慢指针相遇的节点B的长度为（a + b）【这个长度是已知的】。现在我们想知道a的值，注意到快指针fast始终是慢指针slow走过长度的2倍，所以慢指针slow从B继续走（a + b）又能回到B点，如果只走a个长度就能回到节点A。但是a的值是不知道的，解决思路是曲线救国，注意到起点到A的长度是a，那么可以用一个从起点开始的新指针result和从节点B开始的慢指针slow同步走，相遇的地方必然是入环的第一个节点A。 文字有点绕，画个图就一目了然了.

public static ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode result = head;

    boolean hasCycle = false;
    while (fast != null && fast.next != null && slow != null) {
        fast = fast.next.next;
        slow = slow.next;

        //判断是否有环
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (hasCycle) {
        while (result != slow) {
            result = result.next;
            slow = slow.next;
        }
        return result;
    }
    return null;
}

4.两个有序链表合并 (LeetCode 21)

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }

    ListNode temp = new ListNode(0);
    ListNode result = temp;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            temp.next = l1;
            l1 = l1.next;
        } else {
            temp.next = l2;
            l2 = l2.next;
        }
        temp = temp.next;
    }

    //如果l1或者l2任何一个为空，就将另一个直接接在尾部。
    if (l1 == null) {
        temp.next = l2;
    } else {
        temp.next = l1;
    }
    return result.next;
}

5.删除链表的倒数第N个结点 (LeetCode 19)

//解法一，两次遍历。正常的思维是先求出链表的长度，然后从头到尾去遍历。
public static ListNode removeLastN(ListNode head, int n) {
    int len = 0;
    ListNode point = head;

    //遍历链表得出总长度
    while (point != null) {
        point = point.next;
        len++;
    }

    //得到是删除正数第几个
    int k = len - n;
    //指针，指向head

    ListNode point2 = new ListNode(0);
    ListNode result = point2;
    point2.next = head;

    //前面的照常遍历
    for (int i = 0; i <= k; i++) {
        point2 = point2.next;
    }
    //第K个就删除
    point2.next = point2.next.next;
    return result.next;
}

//解法二，一次遍历。这一种解法是利用了快慢指针，一般情况下不太容易想出此种方法。
public static ListNode onceRemoveLastN(ListNode head, int n) {
    //慢指针
    ListNode slow = new ListNode(-1);
    slow.next = head;

    ListNode result = slow;

    //快指针
    ListNode fast = new ListNode(-1);
    fast.next = head;

    while (fast != null) {
        fast = fast.next;
        //快指针先走n步
        if (n < 0) {
            slow = slow.next;
        }
        n--;
    }
    slow.next = slow.next.next;

    return result.next;
}

关于删除链表结点的问题：

• 链表的头和尾这两个结点比较特殊，删除的时候要考虑边界情况。一般我们是用一个指针的next指向这个链表的头。这样头部的特殊情况就可以解决。
• 关于一个结点node的删除我们一般有两种做法：

//方法一：
  preNode.next = preNode.next.next;  //preNode为node的前面一个结点
  
  //方法二：
  node.val = node.next.val;
  node.next = node.next.next;

同样，这两种方法要考虑边界情况。

6.求链表的中间结点 (N等分点)

//二等分代码
public static ListNode halfNode(ListNode head) {
    ListNode fast = new ListNode(0);
    fast.next = head;

    ListNode slow = new ListNode(0);
    slow.next = head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

如果是N等分的话也是用快慢指针的思想，快指针一次性走N步，慢指针一次走一步，最后快指针走到终点的时候，慢指针所在的结点就是N等分点（注意验证一些边界情况)。