枣庄做网站的公司,山西建设厅报名网站,做网站的文案怎么写,wordpress 4.9升级文章目录 LeetCode203. 移除链表元素LeetCode237. 删除链表中的节点LeetCode206. 反转链表ⅠLeetCode92. 反转链表 II思路 1思路 2 LeetCode876. 链表的中间结点剑指 Offer 22. 链表中倒数第k个节点LeetCode21. 合并两个有序链表LeetCode86. 分隔链表LeetCode234. 回文链表Leet… 文章目录 LeetCode203. 移除链表元素LeetCode237. 删除链表中的节点LeetCode206. 反转链表ⅠLeetCode92. 反转链表 II思路 1思路 2 LeetCode876. 链表的中间结点剑指 Offer 22. 链表中倒数第k个节点LeetCode21. 合并两个有序链表LeetCode86. 分隔链表LeetCode234. 回文链表LeetCode160. 相交链表LeetCode141. 环形链表 LeetCode203. 移除链表元素
题目 给你一个链表的头节点 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;
}LeetCode237. 删除链表中的节点
题目 有一个单链表的 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);
}LeetCode206. 反转链表Ⅰ
题目 给你单链表的头节点 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;
}LeetCode92. 反转链表 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;
}LeetCode876. 链表的中间结点
题目 给你单链表的头结点 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;
}LeetCode21. 合并两个有序链表
题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 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;
}LeetCode86. 分隔链表
题目 给你一个链表的头节点 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;
}LeetCode234. 回文链表
题目 给你一个单链表的头节点 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;
}LeetCode160. 相交链表
题目 给你两个单链表的头节点 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;
}LeetCode141. 环形链表
题目 给你一个链表的头节点 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;
}
