链表oj练习

例1

运用前插思想

struct ListNode* reverseList(struct ListNode* head) {struct ListNode*pre=NULL;struct ListNode*cur=head;struct ListNode*tmp=NULL;while(cur){tmp=cur->next;head=cur;cur->next=pre;pre=cur;cur=tmp;}return head;
}

例2

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* new=NULL;struct ListNode* newhead=NULL;while(cur1&&cur2){if(cur1->val<=cur2->val){if(newhead==NULL){newhead=cur1;new=cur1;}else{new->next=cur1;new=cur1;}cur1=cur1->next;}else{if(newhead==NULL){newhead=cur2;new=cur2;}else{new->next=cur2;new=cur2;}cur2=cur2->next;}}if(cur1==0){while(cur2){if(newhead==NULL){newhead=cur2;new=cur2;}else{new->next=cur2;new=cur2;}cur2=cur2->next;}}else{while(cur1){if(newhead==NULL){newhead=cur1;new=cur1;}else{new->next=cur1;new=cur1;}cur1=cur1->next;}}return newhead;}

例子3

#include<stdio.h>
#include<stdlib.h>
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode* lit=NULL;ListNode* big=NULL;ListNode* cur1=NULL;ListNode* cur2=NULL;ListNode* cur=pHead;while(cur){if(cur->val<x){if(lit==NULL){lit=cur;}else{cur1->next=cur;}cur1=cur;cur=cur->next;}else{if(big==NULL){big=cur;}else{cur2->next=cur;}cur2=cur;cur=cur->next;}}if(lit==NULL)return big;cur1->next=big;if(big==NULL)return lit;cur2->next=NULL;return lit;}
};

li4

bool hasCycle(struct ListNode *head) {if(head==0||head->next==0)return 0;struct ListNode *slow=head;struct ListNode *fast=head->next;while(slow!=fast&&fast!=0&&fast->next!=0){fast=fast->next->next;slow=slow->next;}      if(slow==fast)return 1;return 0;
}

尾插适合前哨兵

li5

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{struct ListNode *curb=headB;struct ListNode *cura=headA;int cta=0;int ctb=0;while(cura){cta++;cura=cura->next;}while(curb){ctb++;curb=curb->next;}int len=abs(cta-ctb);if(cta>=ctb){while(len--){headA=headA->next;}}else{while(len--)headB=headB->next;}while(headB){if(headA==headB)return headA;headA=headA->next;headB=headB->next;}return 0;
}

li6

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {ListNode*slow,*fast;slow=A;fast=A;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}ListNode*newhead=NULL;ListNode*cur=slow;ListNode*pre=NULL;while(cur){newhead=cur;cur=cur->next;newhead->next=pre;pre=newhead;}while(newhead){if(A->val!=newhead->val)return 0;A=A->next;newhead=newhead->next;}return 1;}
};