5道链表oj题

这里写目录标题

206. 反转链表

解题思路

指针反转法

这里我们直接把节点的指针进行反转就行，反转的时候要注意保存好下一个节点的地址和上一个节点的地址。
n1表示当前节点的上一个节点的地址
n2表示当前节点
n3表示当期节点的下一个节点的地址

节点插入法
我们创建新的头节点的地址，原链表中的每个节点一个一个进行头插。

代码

指针反转法

structListNode*reverseList(structListNode* head){if(head==NULL)return head;structListNode* n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=head->next;while(n3){
        n2->next=n1;

        n1=n2;
        n2=n3;
        n3=n2->next;}
    n2->next=n1;return n2;}

节点插入法

structListNode*reverseList(structListNode* head){structListNode* newhead=NULL;while(head){structListNode* cur=head;
        head=head->next;
        
        cur->next=newhead;
        newhead=cur;}return newhead;}

876. 链表的中间结点

解题思路

快慢指针法，慢指针走一步，快指针走两步。当快指针指向为空的时候。慢指针指向的节点即为中间的节点。

代码

structListNode*middleNode(structListNode* head){structListNode*low,*quick;
    low=head;
    quick=head;while(quick->next){
        low=low->next;
        quick=quick->next;if(quick==NULL)break;
        quick=quick->next;if(quick==NULL)break;}return  low;}

203. 移除链表元素

解题思路

方法1：遍历链表，遇到val，则跳过该节点。

代码

方法1：

structListNode*removeElements(structListNode* head,int val){structListNode* cur=head;structListNode* curpro=head;while(head&&head->val==val){
            head=head->next;free(cur); 
            cur=head;}while(cur){if(cur->val==val){
            curpro->next=cur->next;free(cur);
            cur=curpro->next;}else{
           curpro=cur;
        cur=curpro->next;}}return head;}

链表中倒数第k个结点

解题思路

快慢指针法，先让快指针走k步，然后快慢指针一起走。直到快指针为空的时候，慢指针指向的节点就是倒数第k个节点。
注意k的值大于节点个数的时候，返回的为空。

代码

structListNode*FindKthToTail(structListNode* pListHead,int k ){structListNode*slow,*quick;
    slow=NULL;
    quick=pListHead;int i=0;while(i<k&&quick){
        quick=quick->next;
        i++;}if(i==k){
        slow=pListHead;while(quick){
        slow=slow->next;
        quick=quick->next;}}return slow;}

21. 合并两个有序链表

解题思路

开辟一个头节点用于当中新的链表，里面不存有效值，对应给的两个链表，从首个节点开始进行val值的比较，小的那个值的节点插入到新的节点的后面，一直到某个链表节点的结尾。把剩下一个链表的全部插入到新链表的后面。最后不要忘记释放头节点。

代码

structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){structListNode* newhead=(structListNode*)malloc(sizeof(structListNode));structListNode* cur=newhead;while(list1&&list2){if(list1->val<list2->val){
            cur->next=list1;
            list1=list1->next;
            cur=cur->next;}else{
            cur->next=list2;
            list2=list2->next;
            cur=cur->next;}}if(list1==NULL){
        cur->next=list2;}else{
        cur->next=list1;}//销毁
    cur=newhead->next;free(newhead);
    newhead=NULL;return cur;}