注：本文章练习题来自牛客和LeetCode，分享的是自己的练习总结

1.给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
1.先不考虑头结点，因为优先考虑头结点值会产生循环处理较为复杂
2.先进行处理后面的普通的结点，如果该结点的值与val相等，则删除，若不相等则继续处理下一个结点，直到处理完所有的结点
3.再处理头结点

/**
 * 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 removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        ListNode prev  = head;
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

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

1.就地翻转，改变的是每个结点的next指向

2.pre引用指向前一个结点，cur引用指向的当前要处理的结点，next引用指向的下一个结点，防止断链

3.处理完所有的结点，返回新的头结点pre

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode curNext = null;
        while(cur != null){
            curNext = cur.next;
            cur.next  = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }

3.给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

1.fast引用的移动速度是slow引用的移动速度的二倍；

2.fast引用最终走的路程肯定也是slow引用的二倍

3.循环执行条件分为链表结点为奇数和偶数的情况，需要特别注意，同时要注意空指针异常

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


    }

4.输入一个链表，输出该链表中倒数第k个结点。

1.判单k位置的合法性和头结点是否为空

2.双引用，fast先走 k - 1 步，之后slow 和 fast 各走一步，保持 k - 1 的差值，直至fast为最后一个结点（k - 1 步 为 你要的倒数第k个结点与倒数第一个结点之间的差值）

3.当k大于链表长度的时候，fast可能早为0，需要进行判断处理

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

    }

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

1.比较两链表中的结点大小，将小结点加入到新的链表中

2.当出现一个链表为空时，需要判断另一个链表是否为空，不空则将加入到后面

 public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        ListNode newNode = new ListNode(-1);
        ListNode tmp = newNode;
        while(headA != null && headB != null){
            if(headA.val < headB.val){
                tmp.next = headA;
                tmp = tmp.next;
                headA = headA.next;
            }else{
                tmp.next = headB;
                tmp = tmp.next;
                headB = headB.next;
            }
        }
        if(headA != null){
            tmp.next = headA;
        }
        if(headB != null){
            tmp.next = headB;
        }
        return newNode.next;

    }

6.现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

1.分为两个链表，前一个链表存放的是小于目标值的元素，后一个链表存放的是大于目标值的元素

2.采用的都是尾插法，因为要保持之前的相对顺序，使用尾插法要注意的是判断当前链表是否为空

3.当前半部分链表为空的时候返回后半部分链表，同时注意最后一个结点可能已经加入到了第一个链表，当第二个链表有元素的时候，一定要手动将第二个链表的最后一个元素的next置为null

 public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead == null){
            return null;
        }
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while(cur != null){
            if(cur.val < x){
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = cur;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        if(bs == null){
            return as;
        }
        be.next = as;
        if(as != null){
            ae.next = null;
        }
        return bs;
    }

7.在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

1.头结点可能进行删除处理，需要创建傀儡结点，使得头结点作为普通节点处理

2.当第一次找到了相同的两个结点，利用有序的链表，判断是否后面还是否有相同的结点，同时注意将cur引用直到不为相同的结点

3.当最后一个结点为重复结点时，tmp结点的next不为空，需要手动置空，否则会报错

public ListNode deleteDuplication(ListNode pHead) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = pHead;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }else{
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;
        return newHead.next;

    }

8.对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

1.找到中间结点的位置

2.将后半部分链表逆置

3.双指针双向遍历判断每个值是否相等，注意奇数和偶数的判断

public boolean chkPalindrome(ListNode A) {
        // write code here
        ListNode slow = A;
        ListNode fast = A;
        while(fast != null  && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode prev = slow;
        ListNode cur = slow.next;
        ListNode curNext = null;
        while(cur != null){
            curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        while(A != null && prev != null){
            if(A.val !=  prev.val){
                return false;
            }
            if(A.next == prev){
                return true;
            }
            A = A.next;
            prev = prev.next;
        }
        return true;
    }

9.给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

1.求出链表长度

2.长链表先移动两个链表之间的差值元素，因为链表相交之后，后面的所有的结点都是相同的

3.比较两个链表的对应元素找到相交的位置

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;

        int count1 = 0;
        while(pl != null){
            count1++;
            pl = pl.next;
        }

        int count2 = 0;
        while(ps != null){
            count2++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = count1 - count2;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = count2 - count1;
        }

        while(len != 0){
            pl = pl.next;
            len--;
        }

        while(pl != null && ps != null && pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        if(pl == ps && pl != null){
            return pl;
        }
        return null;
        
    }

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

1.双引用法，slow每次走一步，fast每次走两步

2.若链表存在环，多次之后肯定可以相遇，判断是否有环

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

11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中

结论：找到相遇的节点后，将一个引用置为head，若存在环，进行多次移动之后，一定可以找到相遇即为环的起始点

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