面试篇：两个面试常见算法题

伊泽瑞尔

发布于 2022-06-01 08:39:05

21300

代码可运行

文章被收录于专栏：大数据与知识图谱大数据与知识图谱

运行总次数：0

代码可运行

1.链表反转

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

方法一：迭代

原链表：1->2->3->null 反转链表：null->3->2->1

在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

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

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。

方法二：递归

假设链表为：N1->N2->...->Ni->Ni+1->...->Nm->null。

若从节点Ni+1到Nm已经被反转，而当前位置为Ni。N1->N2->...->Ni->Ni+1<-...<-Nm。

然后，Ni+1的下一个节点指向Ni。

则，Ni.next.next = Ni。

n1的下一个节点必须指向null，否则，链表中可能会产生环。

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

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

2.二分查找

public static int binSearch(int srcArray[], int key) {   
            int mid = srcArray.length / 2;   
            if (key == srcArray[mid]) {   
                return mid;   
            }   

            int start = 0;   
            int end = srcArray.length - 1;   
            while (start <= end) {   
                mid = (end - start) / 2 + start;   
                if (key < srcArray[mid]) {   
                   end = mid - 1;   
                } else if (key > srcArray[mid]) {   
                    start = mid + 1;   
                } else {   
                    return mid;   
                }   
            }   
            return -1;   
        }

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自大数据与知识图谱微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度