面试篇：两个面试常见算法题
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 删除
评论
登录后参与评论
推荐阅读
目录