文件服务器网站搭建教程,网站那种推广链接怎么做,自治区住房和城乡建设厅网站,如何做带后台的网站目录
#x1f4a1;重排链表
题目描述
方法一#xff1a;
方法二#xff1a;
#x1f4a1;旋转链表
题目描述
方法#xff1a;
#x1f4a1;反转链表||
题目描述
方法#xff1a;
#x1f4a1;总结 #x1f4a1;重排链表
题目描述
给定一个单链表 L 的头节…
目录
重排链表
题目描述
方法一
方法二
旋转链表
题目描述
方法
反转链表||
题目描述
方法
总结 重排链表
题目描述
给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
提示
链表的长度范围为 [1, 5 * 104]1 node.val 1000 方法一 将链表的每一个节点存在数组里然后用下标访问的方式交叉连接。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
void reorderList(struct ListNode* head){if(head-nextNULL||head-next-nextNULL)return;ListNode* arr[50001];ListNode* curhead;int n0;while(cur){arr[n]cur;curcur-next;n;}int i0;int jn-1;while(ij){arr[i]-nextarr[j];i;arr[j]-nextarr[i];j--;}arr[i]-nextNULL;} 方法二 可以先用快慢指针的方法找到链表的中间节点然后将中点后的链表翻转成一个新的链表最后将这个新链表和原链表切割掉中间节点之后的链表合并成一个新的链表合并方式是交叉合并。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
ListNode* MiddleNode(ListNode* head)
{ListNode* fasthead;ListNode* slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;slowslow-next;}return slow;
}
ListNode* ReverseList(ListNode* head)
{ListNode* pheadNULL;ListNode* curhead;while(cur){ListNode* tmpcur-next;//注意先后顺序cur-nextphead;pheadcur;curtmp;}return phead;
}
void reorderList(struct ListNode* head){ListNode* midMiddleNode(head);ListNode* pheadReverseList(mid-next);mid-nextNULL;ListNode* curhead;while(phead){ListNode* nextcur-next;cur-nextphead;ListNode* tmp phead-next;phead-nextnext;pheadtmp;curcur-next-next;}}
旋转链表
题目描述
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
提示
链表中节点的数目在范围 [0, 500] 内-100 Node.val 1000 k 2 * 109 方法 要求每个节点向右移动k位置其实就是将倒数k个结点接在头节点之前倒数第k个结点成为新的头节点但是这里需要对k进行处理因为k可能大于链表长度所以kk%len还有一个需要注意的就是当klen时是不需要进行任何操作的直接返回头节点就可以了。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* rotateRight(struct ListNode* head, int k) {if(headNULL||k0)return head;ListNode* curhead;ListNode* prevhead;ListNode* rethead;int l0;while(ret){retret-next;l;}kk%l;if(k0)return head;while(k--){curcur-next;}while(cur-next){curcur-next;prevprev-next;}ListNode* Nextprev-next;cur-nexthead;prev-nextNULL;return Next;
}
反转链表||
题目描述
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。
提示
链表中节点数目为 n1 n 500-500 Node.val 5001 left right n 方法 我的方法就是将区间[left,right]之间的结点翻转然后与原来区间前后的结点重新连接起来。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head,struct ListNode* tail)
{ListNode*pheadNULL;//新的头ListNode*curhead;while(cur!tail)//遍历原链表{ListNode*nextcur-next;//保存下一个节点的地址避免丢失cur-nextphead;pheadcur;//更新头节点curnext;//继续遍历}return phead;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {ListNode* cur1head;ListNode* cur2head;int cnt1;while(cntleft-1){cur1cur1-next;cur2cur2-next;cnt;}while(cntright){cur2cur2-next;cnt;}ListNode* tailNULL; if(cur2!NULL)tailcur2;if(left1)headreverseList(cur1,cur2);elsecur1-nextreverseList(cur1-next,cur2);while(cur1-next){cur1cur1-next;}cur1-nexttail;return head;
}
总结
链表相关的题目还是要注意细节结点之间的切割与连接要特别仔细不然任意造成空结点或者成环导致死循环。
