预备知识
构建链表——尾插法
ListNode * CreateNode(int n) {
ListNode *head = NULL, *pnew = NULL, *ptail = NULL;
int num, i = 1;
while (i <= n)
{
pnew = new ListNode(0);
cout << "输入第" << i << "个结点:" << endl;
cin >> num;
pnew->val = num;
pnew->next = NULL;
if (head == NULL)
head = pnew;
else
{
ptail->next = pnew;
}
ptail = pnew;
i++;
}
pnew = NULL;
delete pnew;
return head;
}
LeetCode 92
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
//需要逆置的总长度
int change_len = n-m+1;
//初始化开始逆置的节点前驱
ListNode *pre_head = NULL;
//最终转换后的链表头节点
ListNode *result = head;
//将head向前移动m-1个位置
while(head && --m){
//记录head的前驱
pre_head=head;
head=head->next;
}
//modify_list_tail指向逆置后的链表尾
ListNode *modify_list_tail = head;
ListNode *new_head =NULL;
//逆置change_len个节点
while(head && change_len){
ListNode *next =head->next;
head->next=new_head;
new_head=head;
head=next;
change_len--;
}
//链接逆置后的链表尾与逆置段的后一个节点
modify_list_tail->next = head;
//如果pre_head不为空，说明不是从第一个节点开始逆置的
if(pre_head){
pre_head->next = new_head;
}else{
result=new_head;
}
return result;
}
};
LeetCode 21
申请的临时空间只要不和你问题的规模成正比，复杂度就是O(1)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr){
return l2;
}
else if(l2 == nullptr){
return l1;
}
ListNode * head = new ListNode(0);
ListNode * ptr = head;
while(l1 && l2){
if(l1->val < l2->val){
ptr->next = l1;
l1 = l1->next;
}else{
ptr->next = l2;
l2 = l2->next;
}
ptr = ptr->next;
}
if(l1)ptr->next = l1;
else if(l2)ptr->next = l2;
ptr = head;
head = head->next;
delete ptr;
return head;
}
};
leetcode 142
思路一：双指针
这个博客讲得不错：https://blog.csdn.net/zhoufen12345/article/details/76390278
思路二：存储访问过的节点（申请了额外空间，并且时间效率不如方法一）
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> visit;
ListNode * p = head;
while(p&&p->next)
{
if(visit.find(p)==visit.end())
{
visit.insert(p);
p=p->next;
}
else
{
return p;
}
}
return NULL;
}
LeetCode 160
思路1：遍历两个链表，求两个链表的长度差x，下次遍历的时候，让长的那个先走x步，之后查看两个链表有没有访问相同节点的时候，如果有，证明有交点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len1 = 0,len2 = 0;
ListNode *pA,*pB;
pA = headA;
// 统计第一个链表节点数
while(pA){
++len1;
pA = pA->next;
}//while
pB = headB;
// 统计第一个链表节点数
while(pB){
++len2;
pB = pB->next;
}//while
pA = headA;
pB = headB;
// 长度相等且只一个节点一样
if(len1 == len2 && pA == pB){
return pA;
}//if
// pA指向长链表 pB指向短链表
if(len1 < len2){
pA = headB;
pB = headA;
}//if
// pA,Pb指向相同大小位置的节点上
int as = abs(len1- len2);
for(int i = 0;i < as;++i){
pA = pA->next;
}//while
// 比较是不是相交点
while(pA){
if(pA == pB){
return pA;
}//if
pA = pA->next;
pB = pB->next;
}//while
return nullptr;
}
};
思路2：双指针遍历两个链表，当链表B遍历到尾部时，使其next指向链表A的表头；同理，当链表A遍历到尾部时，使其next指向链表B的表头。如此遍历，有重合就证明有交点。最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
// 有空链表肯定无交点
if(pA == nullptr || pB == nullptr){
return nullptr;
}//if
while(pA && pB){
// 交点
if(pA == pB){
return pA;
}
if(pA->next && pB->next){
pA = pA->next;
pB = pB->next;
}
// 到达pA末尾,pB未到达
else if(!pA->next && pB->next){
pA = headB;
pB = pB->next;
}
// 到达pB末尾,pA未到达
else if(pA->next && !pB->next){
pA = pA->next;
pB = headA;
}
// 同时到达pA,pB末尾
else{
return nullptr;
}
}
}
};
LeetCode 86
思路：创建两个指针，小的存一个指针里，大的存另一个，最后将两个链表连接起来。
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *leftHead = (ListNode*)malloc(sizeof(ListNode));
ListNode *rightHead = (ListNode*)malloc(sizeof(ListNode));
//小的都存lpre后面，其余的都存rpre后面。之后把这俩链接就可以了
ListNode *lpre = leftHead,*rpre = rightHead;
while(head != NULL){
if(head->val < x){
lpre->next = head;
//使得lpre指向head，新的小点都查到lpre后面
lpre = head;
}
else{
rpre->next = head;
rpre = head;
}
head = head->next;
}
rpre->next = NULL;
lpre->next = rightHead->next;
return leftHead->next;
}
};
