牛客网

BM1 反转链表

输入 {1,3,4,2,5} 输出

public ListNode reverseList(ListNode head){
    if(head == null){
        return null;
    }
    //设置一个虚拟头节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode cur = head;
    while(cur.next != null){
        ListNode temp = cur.next;
        cur.next = cur.next.next;
        temp.next = dummy.next;
        dummy.next = temp;
    }
    return dummy.next;
}

BM2 链表内指定区间反转

输入 {1,2,3,4,5} 2,4 输出

public ListNode reverseBetween (ListNode head, int m, int n) {
    if(head == null){
        return null;
    }
    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode cur = head;
    ListNode pre = dummy;
    for(int i = 0 ; i < m -1 ;i++){
        pre = pre.next;
        cur = cur.next;
    }
    for(int i = 0 ; i < n-m;i++){
        ListNode temp = cur.next;
        cur.next = cur.next.next;
        temp.next = pre.next;
        pre.next = temp;
    }
    return dummy.next;
}

BM3 链表中的节点每k个一组翻转

输入 {1,2,3,4,5} 2

public ListNode reverseKGroup (ListNode head, int k){
    ListNode cur = head;
    int count = 0;
    while (cur != null && count != k) {
        cur = cur.next;
        count++;
    }
    if (count == k) {
        cur = reverseKGroup(cur, k);
        while (count != 0) {
            count--;
            ListNode tmp = head.next;
            head.next = cur;
            cur = head;
            head = tmp;
        }
        head = cur;
    }
    return head;
}

BM6 判断链表是否有环

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

BM7 判断链表环的入口

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null && pHead.next == null) return null;
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode n1 = slow;
                ListNode n2 = pHead;
                while (n1 != n2) {
                    n1 = n1.next;
                    n2 = n2.next;
                }
                return n1;
            }
        }
        return null;
    }