好的html5网站模板,专题型定制网站建设,做游戏网站要备案吗,做小程序的流程文章目录 LeetCode 203. 移除链表元素LeetCode 237. 删除链表中的节点LeetCode 206. 反转链表ⅠLeetCode 92. 反转链表 II思路 1思路 2 LeetCode 876. 链表的中间结点剑指 Offer 22. 链表中倒数第k个节点LeetCode 21. 合并两个有序链表LeetCode 86. 分隔链表LeetCode 234. 回文… 文章目录 LeetCode 203. 移除链表元素LeetCode 237. 删除链表中的节点LeetCode 206. 反转链表ⅠLeetCode 92. 反转链表 II思路 1思路 2 LeetCode 876. 链表的中间结点剑指 Offer 22. 链表中倒数第k个节点LeetCode 21. 合并两个有序链表LeetCode 86. 分隔链表LeetCode 234. 回文链表LeetCode 160. 相交链表LeetCode 141. 环形链表LeetCode 142. 环形链表 IILeetCode 138. 复制带随机指针的链表 LeetCode 203. 移除链表元素
题目 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。OJ链接 思路 双指针 定义指针 newHead : 返回链表的头结点 tail : 返回链表的尾结点 cur : 用于顺序遍历链表如果有结点的值等于 val , 直接 free 如果有结点的值不等于 val, 将该结点尾插至返回链表\注意不带哨兵位的链表尾插有两种情况: 插入时链表为空 和 插入时链表不为空 实例 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5] 代码实现
struct ListNode* removeElements(struct ListNode* head, int val)
{struct ListNode* newHead; //newHead 指向返回链表的头部struct ListNode* cur; //cur 用于访问原链表struct ListNode* tail; //tail 指向返回链表的尾部cur head; newHead tail NULL;while (cur){if (cur-val val) //如果结点的值等于val, 直接free{struct ListNode* del cur;cur cur-next;free(del);}else{if (tail NULL){newHead tail cur; }else{tail-next cur;tail tail-next;}cur cur-next;}}if (tail)tail-next NULL;return newHead;
}LeetCode 237. 删除链表中的节点
题目 有一个单链表的 head我们想删除它其中的一个节点 node。 给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。 链表的所有值都是 唯一的并且保证给定的节点 node 不是链表中的最后一个节点。 删除给定的节点。注意删除节点并不是指从内存中删除它。这里的意思是 给定节点的值不应该存在于链表中。 链表中的节点数应该减少 1。 node 前面的所有值顺序相同。 node 后面的所有值顺序相同。 OJ链接 思路 将应删除结点的后一个结点的 val 赋值给应删除节点后, 直接删除后面一个节点 实例 把 5结点的 val 修改为 5 下一结点 1 的值, 删除 后一个 1 结点 代码实现
void deleteNode(struct ListNode* node)
{struct ListNode* nodeNext node-next; //得到后面的结点//将后面结点的值赋值到前面一个结点上node-val nodeNext-val;//删除后面的结点node-next nodeNext-next;free(nodeNext);
}LeetCode 206. 反转链表Ⅰ
题目 给你单链表的头节点 head 请你反转链表并返回反转后的链表。OJ链接 思路 定义一个链表指针 newHead NULL, 遍历每个链表结点头插 实例 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 代码实现
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newHead;struct ListNode* cur;newHead NULL;cur head;while (cur){//头插struct ListNode* curNext cur-next;cur-next newHead;newHead cur;cur curNext;}return newHead;
}LeetCode 92. 反转链表 II
题目 给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。OJ链接 思路 1
思路 如果 left 1, 会改变头结点, 定义哨兵结点 dammyNode 找到头结点找到 prev leftNode rightNode succ 四个位置截断出 leftNode 和 rightNode 之间的链表反转该链表, 并通过 prev succ 链接返回 dammyNode-next 实例 输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5] 代码实现
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newHead;struct ListNode* cur;newHead NULL;cur head;while (cur){//头插struct ListNode* curNext cur-next;cur-next newHead;newHead cur;cur curNext;}return newHead;
}struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{struct ListNode* prev, *leftNode;struct ListNode* succ, *rightNode;struct ListNode* cur head;int i 0;//使用哨兵结点, 因为头结点可能发生改变struct ListNode* dummyNode (struct ListNode*)malloc(sizeof(struct ListNode));dummyNode-val -1;dummyNode-next head;//先找到四个位置prev dummyNode;for (i 0; i left - 1; i) //找到prev的位置{prev prev-next;}leftNode prev-next; //找到leftNode的位置rightNode dummyNode;for (i 0; i right; i) //找到leftNode的位置{rightNode rightNode-next;}succ rightNode-next; //找到succ的位置//反转leftNode 和 rightNode 之间的位置rightNode-next NULL;prev-next NULL;reverseList(leftNode);//链接prev-next rightNode;leftNode-next succ;return dummyNode-next;
}思路 2
思路 如果 left 1, 会改变头结点, 定义哨兵结点 dammyNode 找到头结点找到 prev leftNode rightNode succ 四个位置依次将 leftNode-next 移动至 prev-next 直至 leftNode-next succ返回 dummyNode-next 实例 输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5] 代码实现
struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{struct ListNode* prev, *leftNode;struct ListNode* succ, *rightNode;struct ListNode* cur head;int i 0;//使用哨兵结点, 因为头结点可能发生改变struct ListNode* dummyNode (struct ListNode*)malloc(sizeof(struct ListNode));dummyNode-val -1;dummyNode-next head;//先找到四个位置prev dummyNode;for (i 0; i left - 1; i) //找到prev的位置{prev prev-next;}leftNode prev-next; //找到leftNode的位置rightNode dummyNode;for (i 0; i right; i) //找到leftNode的位置{rightNode rightNode-next;}succ rightNode-next; //找到succ的位置while (leftNode-next ! succ) //注意顺序{struct ListNode* prevNext prev-next;struct ListNode* leftNodeNext leftNode-next;prev-next leftNodeNext;leftNode-next leftNodeNext-next;leftNodeNext-next prevNext;}return dummyNode-next;
}LeetCode 876. 链表的中间结点
题目 给你单链表的头结点 head 请你找出并返回链表的中间结点。OJ链接 要求 如果有两个中间结点则返回第二个中间结点。 思路 快慢指针 两个指针 slow 和 fast. slow 每次走一步, fast 每次走两步若结点个数是奇数个, slow处在中间结点的时候, fast-next 指向 NULL 若结点个数是偶数个, slow处在中间结点的时候, fast 指向 NULL 实例 输入head [1,2,3,4,5] 输出[3,4,5] 解释链表只有一个中间结点值为 3 。 代码实现
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow;struct ListNode* fast;slow fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}剑指 Offer 22. 链表中倒数第k个节点
题目 输入一个链表输出该链表中倒数第k个节点。为了符合大多数人的习惯本题从1开始计数即链表的尾节点是倒数第1个节点。OJ链接 思路 快慢指针 slow 和 fast 指向头结点先将 fast 向后移动 k 步slow 和 fast 同时向后直至 fast 指向 NULL注意 k 比链表长度还大的处理 实例 给定一个链表: 1-2-3-4-5, 和 k 2. 返回链表 4-5. 代码实现
struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{struct ListNode* slow head, *fast head;while (k fast){fast fast-next;k--;}if (k){return NULL;}while(fast){slow slow-next;fast fast-next;}return slow;
}LeetCode 21. 合并两个有序链表
题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 OJ链接 思路 双指针 创建虚拟结点 dummyNode 和 返回链表的尾结点 tail遍历两个链表, 值小的结点尾插至返回链表如果有链表还没有遍历完,直接尾插返回 dummyNode-next 实例 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4] 代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 NULL)return list2;if (list2 NULL)return list1;struct ListNode *dummyNode, *tail; //创建虚拟结点 和 链表尾结点dummyNode (struct ListNode*)malloc(sizeof(struct ListNode)); tail dummyNode;while (list1 list2){if (list1-val list2-val){//尾插tail-next list1;list1 list1-next;tail tail-next;}else{//尾插tail-next list2;list2 list2-next;tail tail-next;}}//如果链表还没有遍历完,直接尾插if (list1)tail-next list1;if (list2)tail-next list2;struct ListNode* newHead dummyNode-next;free(dummyNode);return newHead;
}LeetCode 86. 分隔链表
题目 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。OJ链接 要求 你不需要 保留 每个分区中各节点的初始相对位置。 思路 双指针 遍历链表, 值小于 val 的结点, 放入 smallHead 指向的链表;值大于等于 val的结点, 放入 largeHead 指向的链表smallHead 指向的链表尾插 largeHead 指向的链表注意最后的 NULL会更改头结点, 使用虚拟结点 实例 输入head [1,4,3,2,5,2], x 3 输出[1,2,2,4,3,5] 代码实现
struct ListNode* partition(struct ListNode* head, int x)
{if (!head)return NULL;struct ListNode* cur head; //cur 用于遍历链表struct ListNode* large (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* small (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* largeHead large; //虚拟结点指向largestruct ListNode* smallHead small; //虚拟结点指向small//分组while (cur){if (cur-val x) //小于 x 尾插到 small{//尾插small-next cur;small small-next;}else //大于等于 x 尾插到 large{//尾插large-next cur;large large-next;}cur cur-next;}//两链表链接large-next NULL;small-next largeHead-next;return smallHead-next;
}LeetCode 234. 回文链表
题目 给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。OJ链接 思路 快慢指针, 反转链表 使用快慢指针找到链表的中间结点反转中间结点之后的链表从两边向中间遍历,判断是否全部相等 实例 输入head [1,2,2,1] 输出true 代码实现
bool isPalindrome(struct ListNode* head)
{ //找到中间结点struct ListNode* slow head, *fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}//反转中间结点后半部分链表struct ListNode* end NULL;while(slow){struct ListNode* slowNext slow-next;slow-next end;end slow;slow slowNext;}//从头和从尾同时向中间遍历struct ListNode* first head;while (end){if (end-val ! first-val){return false;}end end-next;first first-next;}return true;
}LeetCode 160. 相交链表
题目 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。OJ链接 图示两个链表在节点 c1 开始相交 要求 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须保持其原始结构 。 思路 分别遍历两个链表, 记录两个链表的长度, 最后判断尾结点是否一致.不一致直接返回 false.长链表先走长度差的步数, 随后同时遍历两个链表, 遇到的第一个相同的结点即为相交点 实例 代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA headA, *curB headB;int lenA 0;int lenB 0;//遍历Awhile (curA-next){lenA;curA curA-next;}//遍历Bwhile (curB-next){lenB;curB curB-next;}if (curA ! curB){return NULL;}//计算差值步, 找出长度长的链表int step abs(lenA-lenB);struct ListNode* longNode headA, *shortNode headB;if (lenB lenA){longNode headB;shortNode headA;}//长度长的先走差值步while (step){longNode longNode-next;step--;}//同时遍历两链表while (longNode){if (longNode shortNode){break;}longNode longNode-next;shortNode shortNode-next;}return longNode;
}LeetCode 141. 环形链表
题目 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中存在环 则返回 true 。 否则返回 false 。OJ链接 思路 快慢指针 slow 每次走一步, fast 每次走两步如果 slow fast 有环如果无环, fast会直接出链表 实例 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。 代码实现
bool hasCycle(struct ListNode *head)
{struct ListNode* slow head, *fast head;while (fast fast-next){slow slow-next;fast fast-next-next;if (slow fast){return true;} }return false;
}LeetCode 142. 环形链表 II
题目 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 OJ链接 要求 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。 思路 快慢指针 通过快慢指针找到相遇点两个指针同时从相遇点出发, 速度一致, 相遇点为入环第一个结点 实例 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 代码实现
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow, *fast;struct ListNode* meet;slow fast head;//通过快慢指针, 判断是否有环, 并且找到相遇结点while (fast fast-next){slow slow-next;fast fast-next-next;if (slow fast){meet slow;break;}}//如果fast 或者 fast-next 是NULL, 说明没有环if (!fast || !fast-next)return NULL;// 两相同速度的指针, 分别从头结点 和 相遇结点出发, 第一次相遇点为 入口结点slow head;fast meet;while (slow ! fast){slow slow-next;fast fast-next;}return fast;
}其实还有一个稍微复杂一点的思路, 找到相遇结点后, 直接
newHead slow-next;
slow-next NULL;又回到求两链表交点的问题, 两链表的头结点分别为head 和 newHead LeetCode 138. 复制带随机指针的链表
题目 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。OJ链接 要求 时间复杂度 O ( N ) O(N) O(N), 空间复杂度 O ( 1 ) O(1) O(1) 思路 先将每个结点的复制链接到该节点的 next接着将复制结点的 random 指向 它前一个结点的 random 的 next最后将复制结点尾插入新链表, 恢复原链表链接关系 实例 代码实现
struct Node* copyRandomList(struct Node* head)
{//1. 先将每个结点的复制链接到该节点的 nextstruct Node* cur head;while (cur ! NULL){struct Node* curNext cur-next;//拷贝结点struct Node* copy (struct Node*)malloc(sizeof(struct Node));copy-val cur-val;//链接结点cur-next copy;copy-next curNext;cur curNext;}//2. 接着将复制结点的 random 指向 它前一个结点的 random 的 nextcur head;while (cur ! NULL){struct Node* copy cur-next;//修改复制结点的 randomif (cur-random NULL){copy-random NULL;}else{copy-random cur-random-next;}cur cur-next-next;}//3. 最后将复制结点尾插入新链表, 恢复原链表链接关系struct Node* newHead (struct Node*)malloc(sizeof(struct Node));struct Node* tail newHead;//尾插并恢复原链表链接cur head;while (cur ! NULL){struct Node* copy cur-next;struct Node* curNext copy-next;//尾插tail-next copy;tail tail-next;//恢复原链表链接cur-next curNext;cur curNext;}tail-next NULL;return newHead-next;
}
