【21题,合并两个有序链表】
思路:递归:
1、如果q为NULL,p为NULL;返回NULL;
2、如果q为NULL,返回p;
3、如果p为NULL,返回 q;
4、判断两数大小,p小于等于q返回p,p->next递归调用函数
5、否则返回q,q->next递归调用函数
代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* p = list1;struct ListNode* q = list2;if(q==NULL && p==NULL){return NULL;}else if(q==NULL){return p;}else if(p==NULL){return q;} if(p->val <= q->val){p->next = mergeTwoLists(p->next,q);return p;}q->next = mergeTwoLists(p,q->next); return q;
}
思路:使用迭代的方法
1、定义头尾节点,
2、遍历判断两个链表的单个值,用尾插法将小的值代入链表
代码:
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* p = list1;struct ListNode* q = list2;struct ListNode *tail = NULL;struct ListNode *head = NULL;if(q==NULL && p==NULL){return NULL;}else if(q==NULL){return p;}else if(p==NULL){return q;} while(p != NULL && q!=NULL){struct ListNode *pnew = (q->val <= p->val)? q:p;if(head == NULL){head = pnew;tail = pnew;}else {tail->next = pnew;tail = pnew; }if(q->val <= p->val){q=q->next;}else{p= p->next;}
}tail->next = (q==NULL)?p:q;return head;
}
【环形链表】
思路:暴力求解
1、将所有遍历过的值全部替换为100001
2、判断如果遇到NULL则返回false
3、如果遇到大于100000的数则返回true;
代码:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {if(head == NULL){return false;}struct ListNode *p = head;int temp = 10000;while(1){ p->val = 100001;p = p->next;if(p == NULL){return false;break;}else if(p->val > 100000){return true;break;} }
}