vivo 服务器开发工程师面试题
大家好，我是熊哥。最近熊哥的一个有大厂开发经验的朋友去面试 vivo 的服务器开发工程师（C++） 岗位。
熊哥分享一下该岗位一面的算法题，供大家参考，希望对大家有所帮助。
反转链表
给定一个单链表的头结点 pHead，长度为 n，反转该链表后，返回新链表的表头。
数据范围：n ≤ 1000。
要求：空间复杂度 O(1)，时间复杂度 O(n)。
示例：
当输入链表 {1, 2, 3}时，经反转后，原链表变为 {3, 2, 1}，所以对应的输出为 {3, 2, 1}。
示例
解题思路
由于题目要求空间复杂度 O(1)，时间复杂度 O(n)，因此不能开辟额外空间且只能遍历链表一遍。又由于采用递归法的空间复杂度为 O(n)，所以不能采用递归法求解。
迭代
虽然不能采用递归解法，但可以采用迭代法去求解。迭代法的操作步骤如下：
- 定义两个指针 pre/cur，指向当前节点的后一节点和当前节点，分别用于记录新链表的头节点和遍历整个链表。
- 定义指针 next 用于记录当前节点的下一节点，防止当前节点反转后，找不到其下一节点。
- 遍历整个链表，不断记录当前节点的下一节点，并右移 pre、cur 和 next 指针。
例子
以链表 {1, 2, 3}为例子，其反转的全过程如下动图示。
链表反转过程（迭代法）
注意点
- 链表是空链表，无需反转。
- 链表只有一个节点，无需反转。
说明
定义 next 指针，主要为了避免当前节点反转后，无法再找到当前节点的前一节点，从而无法继续进行反转。
next 指针指向 cur 后面的子链表
如上图示，如果不定义 next 指针，当 cur 指向的节点反转时，断开了 1->2 之间的连接，后续无法再找到子链表 2->3->null，当然也就无法实现该子链表的反转。
复杂度分析
- 时间复杂度：O(n)，其中 n 为链表的长度，需要遍历一遍链表。
- 空间复杂度：O(1)，未开辟额外存储空间。
Show me the Code
C
struct ListNode* reverseList(struct ListNode* head){
/* 边界判断 */
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* pre = NULL;
struct ListNode* cur = head;
while (cur != NULL) {
struct ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
C++
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
Java
ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
Python3
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
pre, cur = None, head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
Golang
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var pre *ListNode = nil
cur := head
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
建议
面试的时候，遇到熟悉的算法题，也不要太兴奋以至于写得飞快。
因为这样面试官会认为你做过该题，当你做完后，面试官往往会额外再给你出一道可能更难的题。
所以如果不是算法大佬，建议就算遇到自己熟悉的题，也要慢慢写，不要自己坑自己哈~~~
补充
本题也可以用递归法去求解，不过时间复杂度为 O(n)，空间复杂度也是 O(n)。
C
struct ListNode* reverseList(struct ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录