刷题-leetcode-字节跳动高频题
发布时间
阅读量：
阅读量
字节跳动研发岗高频考题之链表<持续更新：7月8日>
- 链表
-
- 单一的增删查改（单选题）
- 1. 反转操作（编号：206）
- 2. 处理相交情况的问题（编号：160）
- 3. 处理环状连接的问题（编号：142题）
- 4. 合并两个有序序列的操作（编号：合并两个有序数组）
- 5. 处理多个已排序序列合并的问题（编号：合并K个排序数组）
- 5. 判断或处理回文性质的问题（编号：判断回文数组）
- 6. 深入处理环状连接的问题（编号：深入理解循环数据结构）
- 7. 再次讨论循环连接的技术细节（编号：循环队列的理解与应用）
- 8. 将数组划分为若干组后翻转的操作（编号：分组反转数组技术）
- 9. 区分奇偶特性的技术分析题（编号：奇偶校验与位运算应用）
-
链表
岗位：客户端应用、算法研究与优化、后端开发；题目来源起源于LeetCode；括号内的数字表示相应的LeetCode题号；归纳总结是对相关技术要点的深入分析与系统总结
对于链表问题，在返回结果为头结点的情况下...
为了保证能够正确返回结果，在处理链表相关操作时...
在解决涉及链表的问题的过程中...
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 length(ListNode *head){ //定义一个求链表长度的方法
int len = 0;
while(head->next != NULL){
len++;
head = head->next;
}
return len;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB == NULL) //首先判断是否为空
return headA == NULL ? headA : headB;
int countA , countB ;
ListNode *pa,*pb;
countA = listLen(headA); //计算出来长度
countB = listLen(headB);
for(pa=headA; countA>countB; countA--){ //这两个for循环是将两个链表尾对齐
pa = pa->next;
}
for(pb=headB; countA<countB; countB--){
pb = pb->next;
}
while(pa!= NULL && pa != pb){ //一起向后遍历，找到地址相等的结点
pa = pa->next;
pb = pb->next;
}
return pa;
}
};双指针法
/*A的指针遍历完A 接着从headB开始遍历
B的指针遍历完B 接着从headA开始遍历
两个指针都最多走m + n + 1步。
当两个指针同时为空时，表示不相交；当两个都非空且相等时，表示相交
时间复杂度O(m + n) 空间复杂度O(1)*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL) return nullptr;
ListNode* cur_a = headA;
ListNode* cur_b = headB;
while(cur_a != cur_b)
{
cur_a = (cur_a == nullptr ? headB : cur_a->next);
cur_b = (cur_b == nullptr ? headA : cur_b->next);
}
return cur_a;
}
};3. 环形链表II（142题）
给定一个链表对象，在其中找到首个出现循环的节点。 若该链表无循环结构，则函数返回 null。
为了描述给定链表中的环状结构，我们通过整数 pos 来表示链表尾节点连接到链表中的具体位置（索引起始位置为0）。 当 pos 的值为 -1 时，则表明该链表中不存在任何环状结构。
说明：不允许修改给定的链表。
4. 合并两个有序链表
5. 合并K个排序链表
5.回文链表
6.环形链表
7. 环形链表II
8. K个一组翻转链表
9. 奇偶链表
10. 分隔链表
11.两数相加(2)
给定两个非空链表分别表示两个非负整数。这些链表中的位数是按逆序排列的，并且每个节点仅存储一位数字。将这两个数值相加后将返回一个新的链表来表示它们的总和。假设条件为：除了数字0以外这些数值不会以0开头
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
解决思路：
第一条链表与第二条链表相加的结果也是一个新生成的链表结构；为了实现这一目标，在处理过程中需要对齐对应位进行求和，并考虑进位的情况；由于两条输入的链表可能长度不一，在处理完所有数据节点之后还需检查是否存在未处理完毕的情况；最后还需要判断最高位是否有进位产生；所有计算完成之后检查最高位是否有进位情况并作出相应处理；最终生成的结果即为res
/** * Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *result = new ListNode(-1);//亚节点
if (nullptr == result) {
return nullptr;
}
ListNode *cur = result;
int l1_val = 0;
int l2_val = 0;
int carry = 0;
while (l1 || l2) {
l1_val=l1==nullptr ? 0 : l1->val;
l2_val=l2==nullptr ? 0 : l2->val;
//计算2个链表当前节点的val之和+ 进位carry
int sum = l1_val + l2_val + carry;
carry = sum > 9 ? 1 : 0 ;
//计算新节点值，并设置到result ListNode里
cur->next = new ListNode(sum % 10);
if (nullptr == cur->next) {
return nullptr;
}
//更新cur ListNode，便于后续链接操作
cur = cur->next;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
//如果最后一位的和仍有进位，需要再新建一个Node，来保存carry
if (carry > 0) {
cur->next = new ListNode(carry);
if (nullptr == cur->next) {
return nullptr;
}
}
return result->next;
}全部评论 (0)
还没有任何评论哟~