链表面试题-刷题

第一题：移除链表元素

 首先我们要明确目标，看到是删除链表中 所有 满足的节点，并且返回新的头节点。

public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        } 
        ListNode cur = head.next;
        ListNode pre = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

第二题：反转链表

 第一种方法：使用栈解决

 因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。

public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack= new Stack<>();

    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }

    if (stack.isEmpty())
        return null;

    ListNode node = stack.pop();
    ListNode dummy = node;

    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }

    //最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环
    node.next = null;
    return dummy;
}

第二种方法：双链表求解

双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。

public ListNode ReverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点，保存起来
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，
        head.next = newHead;
        //更新链表
        newHead = head;
        head = temp;
    }
    return newHead;
}

第三题：求链表的中间节点

 快慢指针法，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

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

第四题：链表中倒数第k个节点

还是使用快慢指针，首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点。

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

第五题：合并两个有序链表 

采用递归的思想解题。

每次都用两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

第六题：链表分割

 因为是在原链表上，所以操作会比较繁琐，我这里是把链表分成两段，第一段为小于目标值得，第二段为大于等于目标值的，然后去遍历链表，去判断这个值应该在链表的那个部分，循环结束后把第二段尾插到第一段最后就行了。

public ListNode partition(ListNode head, int x) {
        //小于x的部分
        ListNode bs = null;
        ListNode be = null;
        //大于x的部分
        ListNode as = null;
        ListNode ae = null;

        while (head != null) {
            //判断当前head的val是哪一部分
            if (head.val < x) {
                //判断是否是第一次插入
                if (bs == null) {
                    bs = head;
                    be = head;
                }else {
                    be.next = head;
                    be = be.next;
                }
                head = head.next;
            }else {
                if (as == null) {
                    as = head;
                    ae = head;
                }else {
                    ae.next = head;
                    ae = ae.next;
                }
                head = head.next;
            }
        }
        //链表数据全部大于x
        if (bs == null) {
            return as;
        }
        if (as != null) {
            ae.next = null;
        }
        be.next = as;
        return bs;
    }

第七题：判断链表是否回文

思路：

1. 先判断链表是否为空
2. 前后指针法找中点找中点，设置两个引用fast、slow从头开始走，fast每次走两个节点，slow每次走一个节点，当fast走到链表尾，slow正好走到链表中点。
3. 翻转后段链表
4. .分别从链表头尾两端开始比较，如果遇到val值不一样的情况，则不是回文，否则是回文。

public boolean chkPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode fast = head;
        ListNode slow = head;

        //找到中点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //对比
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

第八题：相交链表

 首先我们需要明白一件事，按照题意那就是相交链表只能是  Y  字型相交。

思路：我们先求出两个链表长度的差距，然后先让长的那个链表先走差值步数，再然后两个链表一起开始向后走，看两链表是否相遇。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //两链表长度
        int lenA = 0;
        int lenB = 0;

        ListNode listLong = headA;//指向长链表，后面不对再换
        ListNode listShort = headB;//短链表

        while (listLong != null) {
            lenA++;
            listLong = listLong.next;
        }
        while (listShort != null) {
            lenB++;
            listShort = listShort.next;
        }

        listLong = headA;
        listShort = headB;
        
        //差值步
        int len = lenA - lenB;
        if (len < 0) {
            listLong = headB;
            listShort = headA;
            len = lenB - lenA;
        }

        //长链表先走差值步
        while (len != 0) {
            listLong = listLong.next;
            len--;
        }

        while (listLong != listShort) {
            listShort = listShort.next;
            listLong = listLong.next;
        }
        if (listLong == null) {
            return null;
        }
        return listLong;
    }

第九题：判断链表是否有环 

思路：还是老样子快慢指针，两指针相遇就是有环

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;
    }