建设银行官方网站个人系统板块,课程设计登录页面,wordpress 网站域名,起名字公司大全免费Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表
二、合并两个有序链表
三、链表分割
四、链表的回文结构 一、反转链表 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1] 输入#xff1a;head [1,2]
输出#xff1a;[2,1]
示例 3#xf…
Yan-英杰的博客 悟已往之不谏 知来者之可追 目录 一、反转链表
二、合并两个有序链表
三、链表分割
四、链表的回文结构 一、反转链表 输入head [1,2,3,4,5]
输出[5,4,3,2,1] 输入head [1,2]
输出[2,1]
示例 3
输入head []
输出[]
提示 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000方法一: 代码解析
struct ListNode* reverseList(struct ListNode* head){if(head NULL){return NULL;}struct ListNode* n1,*n2,*n3;n1 NULL;n2 head;n3 n2-next;while(n2){//翻转链表n2-next n1;//迭代n1 n2;n2 n3;if(n3) n3 n3-next;}return n1;
} 画图解析: 注:该题使用到了三指针 方法二: 代码解析
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur head,*newhead NULL;while(cur){struct ListNode* next cur-next;//头插cur-next newhead;newhead cur;cur next;}return newhead;
} 画图解析 此方法采用头插方式
二、合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]
示例 2
输入l1 [], l2 []
输出[] 示例 3
输入l1 [], l2 [0]
输出[0]
提示 两个链表的节点数目范围是 [0, 50] -100 Node.val 100 l1 和 l2 均按 非递减顺序 排列 代码解析 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if(list1 NULL){return list2;}if(list2 NULL){return list1;}struct ListNode* cur1 list1,*cur2 list2;struct ListNode* head NULL,*tail NULL;while(cur1 cur2){if(cur1-val cur2-val){if(head NULL){head tail cur1;}else{tail-next cur1;tail tail-next;}cur1 cur1-next;}else{if(head NULL){head tail cur2;}else{tail-next cur2;tail tail-next;}cur2 cur2-next;}}if(cur1){tail-next cur1;}if(cur2){tail-next cur2;}return head;
}
画图解析: 三、链表分割 描述 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 思路: 小于尾插到一个链表大于等于尾插到另一个链表再将两个链表链接起来 代码解析: class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode* gGurad,*gTail,*lGuard,*lTail;gGurad gTail (struct ListNode*)malloc(sizeof(struct ListNode));lGuard lTail (struct ListNode*)malloc(sizeof(struct ListNode));gTail-next lTail-next NULL;struct ListNode* cur pHead;while(cur){if(cur-val x){lTail-next cur;lTail lTail-next;}else{gTail-next cur;gTail gTail-next;}cur cur-next;}lTail-next gGurad-next;gTail-next NULL;pHead lGuard-next;free(gGurad);free(lGuard);return pHead;}
}; 画图解析: 此题我们需要用到哨兵位的头节点
四、链表的回文结构 描述 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 测试样例
1-2-2-1
返回true 代码解析 //查找中间节点
struct ListNode* Mid(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* reverse(struct ListNode* Head)
{struct ListNode* cur Head;struct ListNode* phead NULL;while(cur){struct ListNode* next cur-next;cur-next phead;phead cur;cur next;}return phead;
}class PalindromeList {public:bool chkPalindrome(ListNode* A) {struct ListNode* MidList Mid(A);struct ListNode* ReList reverse(MidList);struct ListNode* pphead A;struct ListNode* ppheadR ReList;while(pphead ppheadR){if(pphead-val ! ppheadR-val){return false;}else{pphead pphead-next;ppheadR ppheadR-next;}}return true;}
};画图解析
