字节跳动研发岗高频考题之链表<持续更新：7月8日>

链表0.单链表的增删查改1. 反转链表（206）2. 相交链表（160）3. 环形链表II（142题）4. 合并两个有序链表5. 合并K个排序链表5.回文链表6.环形链表7. 环形链表II8. K个一组翻转链表9. 奇偶链表10. 分隔链表11.两数相加(2)

链表

岗位：客户端、算法、后端 题目来源：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 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 解题思路： 1） 两条链表相加，返回的结果也是链表，故插值从链表末尾添加 2） 对应位数相加，若进10，则用nextSum记为1；不进位时为零； 下一位计算时再加上nextSum; 3） 两条链表可能不相等，结束循环后需要判断是否遍历完，有需要单独遍历，没有则下一步； 4） 两条链表遍历结束后；还要判断最后一位计算完之后nextSum是否为1，为1 还需要在链表后面添加一个为1 的节点。 5） 返回结果链表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; }