顺序表

(1)原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

oj链接
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

双指针

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left++] = nums[right];
            }
        }
        return left;
    }
}

(2)删除有序数组中的重复项

oj链接
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k

双指针

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
            int front = 0;
            int next = 1;
        while(next < nums.length){
            if(nums[front] != nums[next]){
                nums[++front] = nums[next];
            }
            next++;
        }
        return front+1;
    }
}

优化(相邻的元素不同不进行多余的赋值操作)
像[1,2,3,4,5]就不用进行赋值操作

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int front = 0;
        int next = 1;
        while(next < nums.length){
            if(nums[front] != nums[next]){
                if(next - front > 1){
                    nums[front + 1] = nums[next];
                }
                front++;
            }
            next++;
        }
        return front + 1;
    }
}

(3)合并两个有序数组

oj链接
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

从后面开始确定

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while(m>0&&n>0) {
            if(nums1[m-1]>nums2[n-1]) {
                nums1[m+n-1] = nums1[m-1];
                m--;
            } else {
                nums1[m+n-1] = nums2[n-1];
                n--;
            }
        }
         while(n>0) {
            nums1[n-1] = nums2[n-1];
            n--;
        }
    }
}

链表

(1)删除链表中等于给定值 val 的所有节点

oj链接
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null&&head.val==val) {
            head= head.next;
        }
        if(head == null) {
            return null;
        }
        ListNode prev = head;
        while(prev.next!=null) {
            if(prev.next.val==val) {
                prev.next=prev.next.next;
            } else {
                prev=prev.next;
            }
        }
        return head;
    }
}

(2)反转一个单链表

oj链接
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)  return null;
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = head.next;
        while(next != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            next = next.next;
        }
        cur.next = prev;
        return cur;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

(3) 合并两个有序链表

oj链接
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

(4)链表的中间结点

oj链接
给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

快慢指针

慢指针走一步,快指针走两步

while循环条件不能换顺序

class Solution {
    public ListNode middleNode(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while(fast!=null&&fast.next!=null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
    }
}

(5)链表中倒数第k个结点

牛客网链接
输入一个链表，输出该链表中倒数第k个结点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode fast = head;
        ListNode slow = head;
        if(k<=0||head==null) return null;
        while(k-1>0) {
            if(fast.next == null) return null;
            fast = fast.next;
            k--;
        }
        while(fast.next!= null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

(6)分割链表

oj链接
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return null;
        ListNode less = new ListNode(-1);
        ListNode lessHead = less;
        ListNode larger = new ListNode(-1);
        ListNode largerHead = larger;
        while(head != null) {
            if(head.val<x) {
                less.next = head;
                less = less.next;
            } else {
                larger.next = head;
                larger = larger.next;
            }
            head = head.next;
        }
        larger.next = null;
        less.next = largerHead.next;
        return lessHead.next;
    }
}

方法二:

class Solution {
    public ListNode partition(ListNode head, int x) {
         ListNode cur = head;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        //使用cur来遍历 所有的节点
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            } else {
                // >= x
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if (bs == null) {
            return as;
        }
        be.next = as;
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
}

如果bs为null,那么原链表最后一个节点(next是null)是ae,ae的next就不用置为null

(7)输入两个链表，找出它们的第一个公共结点(Y型)

oj链接
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

(8)给你一个链表的头节点 head ，判断链表中是否有环。

oj链接
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针走到链表的末尾。

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可
能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动
一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，
快指针肯定是可以追上慢指针的，即相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null &&  fast.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

(9)给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

oj链接
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。
思路
设链表头部走x步到环的入口， 环有 y 个节点(包括环入口节点)
先跟上一题一样, fast走两步,slow走一步,如果有环的话在环中相遇.
设在环中走了s步(不包括环的入口节点)
那么slow走了x+s步
fast走了x+s+ny(n是圈数)
因为fast走的距离是slow的两倍
所以2(x+s) = x+s+ny
即x=(n-1)*y+(y-s)
让fast从起始位置走,slow从相遇的位置走(n-1)*y+y-s步,他们会在环的入口相遇.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null &&  fast.next !=null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
               fast = head;
               while(fast != slow) {
                   fast = fast.next;
                   slow = slow.next;
               }
               return fast;
            }
        }
        return null;
    }
}

(10)判定链表是否是回文

即正读和倒读一样的链表
牛客网链接
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路
先用快慢指针找到中间节点(奇数中间,偶数第二个中间结点),将中间节点之后的节点反转,一头从头结点,一头从末尾结点开始比较.

奇数的情况

当两个指针相遇的时候返回true

偶数的情况

当第一个节点的下一个节点是第二个节点且相等就返回true

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null) {
            return true;
        }
        ListNode fast = A;
        ListNode slow = A;
        while(fast!=null&&fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode prev = slow;
        ListNode cur =slow.next;
        while(cur!=null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        while(A!=slow) {
            if(A.val!=prev.val) {
                return false;
            }
            //偶数的情况
            if(A.next==prev) {
                return true;
            }
            A=A.next;
            prev=prev.next;
        }
        return true;
    }
}