【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;         }             } }