字节跳动研发岗高频考题之链表<持续更新:7月8日>
链表
岗位:客户端、算法、后端
题目来源:LeetCode;括号里是LeetCode题号
归纳总结:
- 对于链表问题,返回结果为头结点时,通常需要先初始化一个预先指针 pre,该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值,而且链表构造过程需要指针移动,进而会导致头指针丢失,无法返回结果。
- 涉及链表的题现在纸上画出来
0.单链表的增删查改
1. 反转链表(206)
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
解题思路:(双指针)
就以示例为例讲思路吧
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre=NULL;
ListNode *cur=head;
while (cur!=NULL){
ListNode *temp=NULL;
temp = cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
};
2. 相交链表(160)
编写一个程序,找到两个单链表相交的起始节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* 时间复杂度O(n)
*/
class Solution {
public:
int