面试算法题:求两链表公共节点,判断是否有环,升序排序,删除排序后重复元素,合并有序链表,K个一组翻转链表,分隔链表,有序链表转换二叉搜索树,判断单链表是否为回文链表(Java)

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 面试算法题:求两链表公共节点,判断是否有环,升序排序,删除排序后重复元素,合并有序链表,K个一组翻转链表,分隔链表,有序链表转换二叉搜索树,判断单链表是否为回文链表(Java),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

概述

面试常见的算法题。

输入两个链表,找出它们的第一个公共结点。

分析

  1. 链表是否为空
  2. 链表是否是无环链表?是否是单链表?
  3. 如果两个链表存在公共结点,那从公共结点开始一直到链表的结尾都是一样的,因此只需要从链表的结尾开始,往前搜索,找到最后一个相同的结点即可。单向链表,只能从前向后搜索,借助栈来完成。先把两个链表依次装到两个栈中,然后比较两个栈的栈顶结点是否相同,如果相同则出栈,如果不同,那最后相同的结点就是公共节点。
  4. 先求2个链表的长度,让长的先走两个链表的长度差,然后再一起走,直到找到第一个公共结点。
  5. 由于2个链表都没有环,可以把第二个链表接在第一个链表后面,这样就把问题转化为求环的入口节点问题。
  6. 两个指针p1和p2分别指向链表A和链表B,它们同时向前走,当走到尾节点时,转向另一个链表,比如p1走到链表A的尾节点时,下一步就走到链表B,p2走到链表B的尾节点时,下一步就走到链表A,当p1==p2时,就是链表的相交点

code

@Slf4j
public class FirstCommonNode {

    /**
     * 两个链表的第一个公共结点
     */
    public static ListNode findFirstCommonNode(ListNode current1, ListNode current2) {
        HashMap<ListNode, Integer> hashMap = new HashMap<>(16);
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2)) {
                return current2;
            } else if (getNoLoopLength(current2) == 1) {
                // 链表2长度为1的特殊情况
                return null;
            }
            current2 = current2.next;
        }
        return null;
    }

    /**
     * 无环单链表长度
     */
    private static int getNoLoopLength(ListNode head) {
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        return length;
    }

    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

判断链表是否有环

/**
 * 判断给定链表是否有环
 */
public static boolean hasLoop(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (true) {
        if (fast == null || fast.next == null) {
            // fast走到链表尾
            return false;
        } else if (fast.next == slow || fast == slow) {
            return true;
        } else {
            slow = slow.next;
            fast = fast.next.next;
        }
    }
}

删除链表元素

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

public static ListNode removeElements(ListNode head, int val) {
    ListNode top = new ListNode(0);
    top.next = head;
    ListNode pre = top;
    ListNode temp = head;
    while (temp != null) {
        if (temp.val == val)
            pre.next = temp.next;
        } else {
            pre = temp;
        }
        temp = temp.next;
    }
    return top.next;
}

升序排序


删除排序链表中重复元素

 public static ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode prev = head;
    ListNode p = prev.next;
    while (p != null) {
        if (p.val != prev.val) {
            prev.next = p;
            prev = p;
        }
        p = p.next;
    }
    prev.next = p;
    return head;
}

合并两个有序链表


K个一组翻转链表

给定一个链表,每 k 个节点一组进行翻转,返回翻转后的链表。k为小于或等于链表长度的正整数。如果节点总数不是 k 的整数倍,最后剩余的节点保持原有顺序。

public static ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) {
        return null;
    }
    ListNode b = head;
    for (int i = 0; i < k; i++) {
        if (b == null) {
            return head;
        }
        b = b.next;
    }
    ListNode newHead = reverse(head, b);
    head.next = reverseKGroup(b, k);
    return newHead;
}

private static ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null;
    cur = a;
    nxt = a;
    while (nxt != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}

分隔链表

给定一个链表头节点 head 和一个特定值val,把所有小于val的节点都放置在大于或等于val的节点之前。保留两个分区中每个节点的初始相对位置。

public static ListNode partition(ListNode head, int x) {
    ListNode tmpHead1 = new ListNode(0);
    ListNode tmpHead2 = new ListNode(0);
    ListNode node1 = tmpHead1;
    ListNode node2 = tmpHead2;
    while (head != null) {
        if (head.val < x) {
            node1.next = head;
            head = head.next;
            node1 = node1.next;
            node1.next = null;
        } else {
            node2.next = head;
            head = head.next;
            node2 = node2.next;
            node2.next = null;
        }
    }
    node1.next = tmpHead2.next;
    return tmpHead1.next;
}

有序链表转换二叉搜索树

给定一个升序单链表,将其转换为高度平衡的二叉搜索树,即二叉树每个节点的左右两个子树的高度差的绝对值不超过1。注意:满足条件的二叉搜索树不止一个。

public static TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
        return null;
    }
    return helper(head, null);
}

private static TreeNode helper(ListNode start, ListNode end) {
    if (start == end) {
        return null;
    }
    ListNode slow = start;
    ListNode fast = start;
    while (fast != end && fast.next != end) {
        slow = slow.next;
        fast = fast.next.next;
    }
    TreeNode root = new TreeNode(slow.val);
    root.left = helper(start, slow);
    root.right = helper(slow.next, end);
    return root;
}

判断单链表是否为回文链表

public static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }
    ListNode slow = head;
    ListNode quick = head;
    while (quick != null && quick.next != null) {
        quick = quick.next.next;
        slow = slow.next;
    }
    ListNode pre = null;
    ListNode p = slow;
    while (p != null) {
        ListNode temp = p.next;
        p.next = pre;
        pre = p;
        p = temp;
    }
    while (pre != null) {
        if (pre.val == head.val) {
            pre = pre.next;
            head = head.next;
        } else {
            return false;
        }
    }
    return true;
}

拓展

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142085.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!