leetcode刷题----单链表oj题

4.链表中倒数第k个节点​编辑

5.合并有序链表

6.链表分割

7.链表的回文

8.链表的环

4.链表中倒数第k个节点

---

仿照快慢指针求解中间节点，注意单独处理k>链表表长的情况

---

struct ListNode* getKthFromEnd(struct ListNode* head, int k)
{
    struct ListNode*fast,*slow;
    fast=slow=head;
 
    //fast先走k步
    while(k--)
    {
        //表长小于k，则fast为空
        if(fast==NULL)
        {
            return NULL;
        }
        else
        {
             fast=fast->next;
        }
       
    }
 
    //fast slow一起走
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

5.合并有序链表

题目描述

---

方法：归并

从头比较，取小的尾插到新链表，当有一个链表为空时，结束。

---

 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
    {
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
 
    struct ListNode*head,*tail;
    head=tail=NULL;
    while(l1&&l2)
    {
         if(l1->val<l2->val)
             {
                if(tail==NULL)
                    {
                     head=tail=l1;
                     }
                else
                {
                  tail->next=l1;
                   tail=tail->next;
                  }
              l1=l1->next;
              }
         else
        {
                if(tail==NULL)
                    {
                      head=tail=l2;
                        }
                 else
                     {
                         tail->next=l2;
                         tail=tail->next;
                     }
                  l2=l2->next;
         }
    }
    if(l1)
    {
    tail->next=l1;
    }
    if(l2)
    {
    tail->next=l2;
    }
return head;
}

上面这种也可以加一个带哨兵位的头节点，这样就不用判断tail是否为空的情况，开头的那段判断也可以不用

 struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
    {
   
    struct ListNode*head,*tail;
    head=tail=(struct ListNode*)malloc(sizeof( struct ListNode));
    tail->next=NULL;
    while(l1&&l2)
    {
         if(l1->val<l2->val)
             {
               
                  tail->next=l1;
                   tail=tail->next;
        
              l1=l1->next;
              }
         else
        {
                 tail->next=l2;
                tail=tail->next;
 
                l2=l2->next;
         }
    }
    if(l1)
    {
    tail->next=l1;
    }
    if(l2)
    {
    tail->next=l2;
    }
     struct ListNode*list=head->next;
     free(head);
return list;
}

6.链表分割

题目描述

---

思路：设置两个带哨兵位的头节点的链表，一个储存比x大的数据，一个储存比x小的数据，最后将两个链表链接起来

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* partition(struct ListNode* head, int x){
    //产生两个带哨兵位的头节点
    struct ListNode*lesshead,*lesstail,*greaterhead,*greatertail;
    lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lesstail->next=NULL;
    greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
    greatertail->next=NULL;   
 
    struct ListNode*cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            //插入less
            lesstail->next=cur;
            lesstail=lesstail->next;
        }
        else
        {
             //插入greater
            greatertail->next=cur;
            greatertail=greatertail->next;
        }
        cur=cur->next;
    }
//链接两个链表
lesstail->next=greaterhead->next;
greatertail->next=NULL;//可以避免链表成环问题
 
struct ListNode*newhead=lesshead->next;
free(greaterhead);
free(lesshead);
 
return newhead;
 
}

7.链表的回文

题目描述

---

思路：

1.找到中间节点

2.将后半段逆置

3.依次比较

---

8.相交链表

题目描述思路：

1.容易发现若两个链表相交，则他们一定有共同的尾节点因为节点的next只能有一个位置

2.主要问题在于保持其原本结构《==》破坏后要恢复

---

方法

求A的长度lenA,求B的长度lenB.长的A先走差距步,

---

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL)
    return NULL;
 
    struct ListNode *curA=headA;
    struct ListNode *curB=headB; 
    int lenA=1,lenB=1;
    //求表A的长同时找到A的尾节点
    while(curA)  
    {
        curA=curA->next;
        lenA++;
    }
    
    //求表B的长同时找到B的尾节点
    while(curB)  
    {
        curB=curB->next;
        lenB++;
    }
 
    if(curA!=curB)
    return NULL;
 
    //求第一个交点
    //假设A是短链表，B是长链表
    struct ListNode *shortlist=headA;struct ListNode *longlist=headB;
    //修正
    if(lenA>lenB)
    {
        longlist=headA;
        shortlist=headB;
    }
 
    //长的先走gap步
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longlist=longlist->next;
    }
 
    //一起后移
    while(shortlist!=longlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
return shortlist;
}

8.环形链表

思路：类比位移追及问题

bool hasCycle(struct ListNode *head)
 {
    struct ListNode *fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        return true;
    }
    return false;
}