写在前面

开个贴记录一下 刷题的过程，目前参照 leetcode101，目标101题，由于太久没写java了，也会涉及到一些java的基础用法，希望能和大家共勉吧～

已刷链接：

• 贪心算法：https://www.nowcoder.com/discuss/1051877
• 双指针：https://www.nowcoder.com/discuss/1057237
• 二分查找：https://www.nowcoder.com/discuss/1059986
• 排序：链接
• 搜索：链接
• 动态规划：https://www.nowcoder.com/discuss/1071676
• 分治法：https://www.nowcoder.com/discuss/1091335

链表

No.1 Reverse Linked List

题目：https://leetcode.com/problems/reverse-linked-list/

非递归：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = previous;
            previous = head;
            head = next;
        }
        return previous;
    }
}

递归：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        return reverse(head,previous);
    }
    private ListNode reverse(ListNode head, ListNode pre) {
        if (head == null) {
            return pre;
        }
        ListNode next = head.next;
        head.next = pre;
        return reverse(next,head);
    }
}

No.2 Merge Two Sorted Lists

题目：https://leetcode.com/problems/merge-two-sorted-lists/

非递归：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode mergeList = new ListNode(0);
        ListNode current = mergeList;
        while(list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        current.next = list1 == null ? list2 : list1;
        return mergeList.next;
    }
}

递归：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list2 == null) return list1;
        if (list1 == null) return list2;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

No.3 Swap Nodes in Pairs

题目：https://leetcode.com/problems/swap-nodes-in-pairs/

解题思路：

注意第一次交换不用链接previous，但是后续需要链接previous

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode res = head;
        if (head != null && head.next != null) {
            ListNode swap = head.next;
            head.next = swap.next;
            swap.next = head;
            res = swap;
            ListNode pre = head;
            head = head.next;
            while (head != null && head.next != null) {
                ListNode swapp = head.next;
                head.next = swapp.next;
                swapp.next = head;
                pre.next = swapp;
                pre = head;
                head = head.next;
            }
        }
        return res;
    }
}

No.4 Intersection of Two Linked Lists

题目：https://leetcode.com/problems/intersection-of-two-linked-lists/submissions/

解题思路：

令A到相交处的长度为a，B到相交处的长度为b，相交处到链表尾部的长度为c。a和b开头各一个指针，以相同的速度行走，走到头以后交换至另一个链表头，有走过的长度a+c+b = b+c+a，会在c1处相遇。

记得要处理不相交的情况，所以要允许node走到结尾为null的情况，不然会死循环。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode curA = headA, curB = headB;
        while (curA != curB) {
            if (curA != null) {
                curA = curA.next;
            } else {
                curA = headB;
            }
            if (curB != null) {
                curB = curB.next;
            } else {
                curB = headA;
            }
        }
        return curA;
    }
}

No.5 Palindrome Linked List

题目：https://leetcode.com/problems/palindrome-linked-list/

算法解析：

先快慢指针求出中点，然后反转后半部分list，反转后进行对比

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow.next = reverseList(slow.next);
        slow = slow.next;
        while (slow != null) {
            if (slow.val == head.val) {
                head = head.next;
                slow = slow.next;
            } else {
                return false;
            }
        }
        return true;
    }
    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

No.6 Remove Duplicates from Sorted List

题目：https://leetcode.com/problems/remove-duplicates-from-sorted-list/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

No.7 Odd Even Linked List

题目：https://leetcode.com/problems/odd-even-linked-list/

题目解析：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) return head;
        ListNode even = new ListNode(0);
        ListNode cur = head, ec = even, pre = null;
        while (cur != null && cur.next != null) {
            ec.next = cur.next;
            cur.next = cur.next.next;
            ec = ec.next;
            ec.next = null;
            pre = cur;
            cur = cur.next;
        }
        if (cur == null) {
            pre.next = even.next;
        } else {
            cur.next = even.next;
        }
        return head;
    }
}

No.8 Remove Nth Node From End of List

题目：https://leetcode.com/problems/remove-nth-node-from-end-of-list/

解题思路：

利用快慢指针，让fast指针比slow指针快n个，然后再同步走，这样slow和fast之间永远差n，当fast到底时slow就在可以删除的位置

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode fast = pre,slow = pre;
        for (int i = 0; i < n; i ++) {
            fast = fast.next;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return pre.next;
    }
}

No. 9 Sort List

题目：https://leetcode.com/problems/sort-list/

思路解析：

先用快慢指针求出中点，然后用使用归并排序。注意列表的排序经常使用归并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head, slow = head, temp = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            temp = slow;
            slow = slow.next;
        }
        temp.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        return mergeSort(left, right);
    }
    private ListNode mergeSort(ListNode l, ListNode r) {
        ListNode res = new ListNode();
        ListNode p = res;
        while (l != null && r != null) {
            if (l.val < r.val) {
                p.next = l;
                l = l.next;
            } else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
        }
        p.next = l == null ? r : l;
        return res.next;
    }
}