定义链表至少需要包含:单个节点的数据类型、next指针
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
链表容易扩大和缩小,比vector的优势是插入和从中间删除的速度快。
由节点的==指针==取值用head->val
,由节点取值用head.val
。
静态建立:ListNode dummy(0)
是在栈上定义对象,在栈中分配内存。栈由编译器自动分配释放。
动态建立:tail->next=new ListNode(0)
是在堆上定义对象,在栈中只保留了指向该对象的指针。堆上的对象需要自己分配释放,要小心内存泄漏的问题。
C++中栈和堆上建立对象的区别:https://www.cnblogs.com/xiaoxiaoqiang001/p/5557704.html
做题切记:
迭代:设三个prev、cur、temp往后滑,每次让cur指向prev
递归:递归代码包括三部分:结束条件、过程操作、返回值。写代码时先把结束条件
和递归调用本函数
写上。然后补其他的。
简单思路:注意创建ListNode的时候,是要创建一个占一块空间的节点,还是只创建一个指针。赋值的时候,是赋值指针,还是赋值整个节点(结构体)
递归(包括减而治之和分而治之)==写递推公式==,减而治之,原问题=一个平凡问题+一个规模变小的问题:
迭代法:简单,注意各种各样的测试用例
递归:以后写题要优先考虑递归了
简单思路:先遍历一遍链表得到链表长度,然后再遍历一遍找到对应位删除。
双指针:在链表前加一个dummy节点
使用递归,一发AC,思路就是83+206
自己写的,直接在源节点上操作。要注意节点是动态建立还是静态建立的区别,否则会出bug。
别人的:新建一个链表,而不是改变原来的节点。
学到了一种简便代码的写法:
sum+=(l1?l1->val:0)+(l2?l2->val:0);
l1=(l1 ? l1->next:NULL);
l2=(l2 ? l2->next:NULL);
自己写的:先反转链表,然后同2一样求和
别人的:先把链表的值压入栈中。要注意结果的正反。
自己的:用了栈,一发AC
别人的:以 O(1) 的空间复杂度来求解。切成两半,把后半段反转,然后比较两半是否相等。
学到一种统计链表长度的简便写法:
int len=0;
for(ListNode* head=root;head;head=head->next) ++len;
自己写的:写flag
别人的:双层循环。prev和head
自己写的:prev,cur,temp向后滑动。最后分情况处理奇和偶的连接
其他做法:单独建两个新的链表
//160
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL ||headB==NULL) return NULL;
ListNode *a=headA, *b=headB;
while(a!=b)
{
a=(a?a->next:headB);
b=(b?b->next:headA);
}
return a;
}
//206
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode *cur=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return cur;
}
//21
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
if(l2==NULL) return l1;
if(l1->val <= l2->val)
{
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}
else
{
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}
}
//83
ListNode* deleteDuplicates(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
head->next=deleteDuplicates(head->next);
return head->val==head->next->val?head->next:head;
}
//19
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next=head;
ListNode *fst=&dummy, *scd=&dummy;
while(n--)
fst=fst->next;
while(fst->next)
{
fst=fst->next;
scd=scd->next;
}
scd->next=scd->next->next;
return dummy.next;
}
//24
ListNode* swapPairs(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
head->next->next=swapPairs(head->next->next);
ListNode *temp=head->next->next, *ans=head->next;
head->next->next= head;
head->next=temp;
return ans;
}
//2
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum=0;
ListNode dummy(0);
ListNode *cur=&dummy;
while(l1 || l2 ||sum)
{
sum+=(l1?l1->val:0)+(l2?l2->val:0);
cur->next=new ListNode(sum%10);
cur=cur->next;
sum/=10;
l1=l1?l1->next:NULL;
l2=l2?l2->next:NULL;
}
return dummy.next;
}
//445
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> a,b;
while(l1){
a.push(l1->val);
l1=l1->next;
}
while(l2){
b.push(l2->val);
l2=l2->next;
}
int sum=0;
ListNode dummy(0);
ListNode *cur=NULL;
while(!a.empty()||!b.empty()||sum)
{
sum+=(a.empty()?0:a.top())+(b.empty()?0:b.top());
if(!a.empty()) a.pop();
if(!b.empty()) b.pop();
cur=new ListNode(sum%10);
cur->next=dummy.next;
dummy.next=cur;
sum/=10;
}
return dummy.next;
}
//234
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL) return true;
stack<int> temp;
int len=0;
for(ListNode *cur=head;cur;cur=cur->next,len++) temp.push(cur->val);
len/=2;
while(len--)
{
if(temp.top()!=head->val)
return false;
head=head->next;
temp.pop();
}
return true;
}
//725
vector<ListNode*> splitListToParts(ListNode* root, int k) {
vector<ListNode*> rst(k);
int part_len=0,r=0,len=0;
for(ListNode* head=root;head;head=head->next) ++len;
part_len=len/k;
r=len%k;
ListNode *head=root, *prev=NULL;
for(int i=0;i<k;i++)
{
rst[i]=head;
for(int j=1;j<=(r<=0?part_len:(part_len+1));j++)
{
prev=head;
head=head->next;
}
if(prev) prev->next=NULL;
r--;
}
return rst;
}
//328
ListNode* oddEvenList(ListNode* head) {
if(head==NULL||head->next==NULL||head->next->next==NULL) return head;
ListNode *ji=head, *ou=head->next;
ListNode *prev=head, *cur=head->next, *temp=head->next->next;
int i=1;
for(i=1;temp;i++)
{
prev->next=temp;
prev=cur;
cur=temp;
temp=temp->next;
}
if(i%2==0)
{
prev->next=NULL;
cur->next=ou;
}
else
prev->next=ou;
return ji;
}