网站建设所需,网站布局软件,双11主机 wordpress 2015,宿迁住房和城乡建设部网站目录
一、回文链表
二、 重排链表
三、旋转链表 一、回文链表
给你一个单链表的头节点 head #xff0c;请你判断该链表是否为回文链表。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 1#xff1a; 输入#xff1a;head [1,2,2,1] 输…目录
一、回文链表
二、 重排链表
三、旋转链表 一、回文链表
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 1 输入head [1,2,2,1] 输出true 示例 2 输入head [1,2] 输出false 提示 链表中节点数目在范围[1, 10^5] 内 0 Node.val 9
进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
代码实现
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast ! NULL fast-next ! NULL){slow slow-next;fast fast-next-next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pre NULL;struct ListNode* cur head;while (cur ! NULL){struct ListNode* after cur-next;cur-next pre;pre cur;cur after;}return pre;
}
bool isPalindrome(struct ListNode* head)
{// 1. 找到中间结点如果有两个中间结点则找到第二个中间结点struct ListNode* mid middleNode(head);// 2. 从中间结点开始对后半段进行反转struct ListNode* rightHead reverseList(mid);// 3. 进行前半段和后半段的比较struct ListNode* leftCur head;struct ListNode* rightCur rightHead;while (rightCur ! NULL){if (leftCur-val ! rightCur-val){return false;}leftCur leftCur-next;rightCur rightCur-next;}return true;
} 回文结构是一个生物学名词。双链 DNA 中含有的两个结构相同、方向相反的序列称为回文结构每条单链以任一方向阅读时都与另一条链以相反方向阅读时的序列是一致的。 palindrome n. 回文结构回文序列 牛津a word or phrase that reads the same backwards as forwards, for example madam. 二、 重排链表
给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为 L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
示例 1 输入head [1,2,3,4] 输出[1,4,2,3] 示例 2 输入head [1,2,3,4,5] 输出[1,5,2,4,3] 提示 链表的长度范围为 [1, 5 * 10^4] 1 node.val 1000
代码实现
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pre NULL;struct ListNode* cur head;while (cur ! NULL){struct ListNode* after cur-next;cur-next pre;pre cur;cur after;}return pre;
}
void reorderList(struct ListNode* head)
{// 1. 找到中间结点如果有两个中间结点则找到第二个中间结点struct ListNode* mid middleNode(head);// 2. 从中间结点开始对后半段进行反转struct ListNode* rightHead reverseList(mid);// 3. 重排链表struct ListNode* leftCur head;struct ListNode* rightCur rightHead;while (rightCur-next ! NULL){struct ListNode* leftAfter leftCur-next;struct ListNode* rightAfter rightCur-next;leftCur-next rightCur;rightCur-next leftAfter;leftCur leftAfter;rightCur rightAfter;}
}
图解示例二 三、旋转链表
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
示例 1 输入head [1,2,3,4,5], k 2 输出[4,5,1,2,3] 示例 2 输入head [0,1,2], k 4 输出[2,0,1] 提示 链表中节点的数目在范围 [0, 500] 内 -100 Node.val 100 0 k 2 * 109
代码实现
struct ListNode* rotateRight(struct ListNode* head, int k)
{if (head NULL){return NULL;}// 1. 找到链表的尾结点并计算它的长度struct ListNode* tail head;int len 1;while (tail-next ! NULL){len;tail tail-next;}// 2. 找到倒数第 (k % len 1) 个结点k % len;if (k 0){return head;}struct ListNode* pre head;for (int i 0; i len - k - 1; i){pre pre-next;}// 3. 旋转链表tail-next head; // (1)head pre-next; // (2)pre-next NULL; // (3)return head;
}
