[数据结构与算法]【C语言】图解链表经典例题

注：所有题目均默认链表不带头结点

1. 删除链表中等于给定值 val 的所有节点。

1. 删除值为val的节点，显然我们得找到其前驱节点prev,再将val->next链接至val->next
   
2. 我们还要注意一些特殊情况，当链表为空的时候，当链表头结点的值为val时，我们找前驱节点的方法是失效的。

void removeElements(SLTNode** pphead, SLTDataType val)//去除特定数据
{
	assert(pphead);
	assert(*pphead);//链表为空时结束
	while ((*pphead)->data == val)//头结点的值为val
	{
		*pphead = (*pphead)->next;
	}
	SLTNode* prev = *pphead;
	while (prev->next)
	{
		if (prev->next->data == val)
		{
			prev->next = prev->next->next;
			free(prev->next);
			prev->next = NULL;
		}
		else
		{
			prev = prev->next;
		}
	}
}

当然，我们也可以采用其他的方法：

1. 建立一个空的头结点，链接在链表前面，这样就不用分类讨论了
2. 建立一个新的链表，把值为val的节点加入进来

2. 反转一个单链表

看到这道题，第一时间应该会想到 定义两个指针，从表头开始，依次反转两个节点之间指针的方向：

这样想的方向是正确的，但会存在一个问题：

当我们反转指针,即 b->next=a,那么当我们想向后移动指针的时候，会发现我们已经找不到b右边的节点，所以，在我们反转指针之前，还必须保存一下b->next.

同时，我们还要考虑到其他几个细节：

• 反转后的尾节点指向NULL,而尾节点就是原链表的头节点，我们如何达到这样的效果？
  
  很简单，只要我们将a指针初始位置指向NULL即可。
  循环的终止该如何判定？

看图说话，我们可以观察最后几步指针的位置，我们猜测几种结束方式：

• while?, 如图1，这样指针无法对最后两个节点操作
• while(a), 如图2，此时b为空，无法指向a
• while(b), 如图1, 符合条件，当然，也可以写成while(a->next)

struct ListNode* reverseList(struct ListNode* head)
{

      if(head==NULL)
      return head;
      if(head->next==NULL)
      return head;

     struct ListNode*a=NULL;
     struct ListNode*b=head;
     struct ListNode*c=head->next;

     while(b)
     {
         b->next=a; 
         a=b;
         b=c;

         if(c)
         c=c->next;
     }
     return a;
}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

看到这道题，大多数人的想法肯定是先遍历一次链表，算出节点数目，再减半遍历到中间节点，这样没错，但感觉有些笨重，这里提供一个巧妙的方法：快慢指针法。

什么是快慢指针法？简单来说，定义两个指针，快指针一次走两步，慢指针一次走一步，当快指针走到链表的尾部时，慢指针刚好走到其一般的路程，也就是链表的中间节点。

当然，当链表有偶数个节点的时候，我找的的是第n/2 + 1个节点。

struct ListNode* middleNode(struct ListNode* head){
       if(head==NULL)
       return head;

       struct ListNode* slow=head;
       struct ListNode* fast=head;

       while(fast&&fast->next)
       {
           slow=slow->next;
           fast=fast->next->next;
       }
       return slow;
}

4. 输入一个链表，输出该链表中倒数第k个结点。

关于这道题，我们依旧要用到快慢指针法：

当然这个快慢不是指移动速度上的快慢，而是指出发时间的先后。我们先让快指针走k步，然后快慢指针同时启动，当快指针走到尾的时候，慢指针恰好和快指针差k步，也就是链表的倒数第k个指针。

当然这里还是有几个细节值得我们注意：

1. k的值大于链表长度，该如何处理？

当k的之太大时，我们默认k等于链表长度，也就是说，我们最多让快指针走到尾节点就停止。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    // write code here
    if(k==0)
        return NULL;
    if(pListHead==NULL)
        return NULL;
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    
    while(k--)
    {
        if(fast==NULL)
            return NULL;
        
        fast=fast->next;
    }
    
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
}
    return slow;
}

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

这道题考虑到两个链表已经排好序，我们可以建立一个新的链表，通过依次比较将节点放入新链表中。

这是初始状态，之后我们建立新的链表：比较a->val和b->val的值的大小，将小的值作为新链表的头节点。

同时，我们要注意，我们的新链表还要一个尾节点，因为之后我们得返回newhead，所以在我们要尾插，又不想每次遍历链表找尾节点，那么，我们就需要一个尾指针记录最后节点的位置。

然后，我们将a指针后移，在与b指针比较。

比较之后：

之后以此类推即可，当两个链表中的一个走到底的时候停止。停止之后，我们将还未放在新链表的节点尾插在新链表最后即可。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){

              if(l1==NULL)
              {
                  return l2;
              }
              if(l2==NULL)
              {
                  return l1;
              }

              struct ListNode*a=l1;
              struct ListNode*b=l2;

              struct ListNode*newNode=NULL;
              struct ListNode*tail=NULL;

              
            while(a&&b)
            {
              if(a->val<b->val)
              {
                  if(tail==NULL)
                  {
                      newNode=tail=a;
                  }
                  else
                  {
                      tail->next=a;
                      tail=a;
                      
                  }
                  a=a->next;
              }
              else
              {
                  if(tail==NULL)
                  {
                      newNode=tail=b;
                  }
                  else
                  {
                      tail->next=b;
                      tail=b;
                  }
                  b=b->next;
              }

            }

            if(a)
            
                tail->next=a;
            
            if(b)
            
                tail->next=b;
            
            return newNode;
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

这道题的思路很明确：将小于x的节点放在一个链表中，将大于x的节点放在另一个链表中，最后将两个链表链接起来。

这一题和上一题有异曲同工之妙，都是通过“牺牲空间换取时间”，对于建立的新链表，有两种选择：

1. 无空头结点的链表
对于这种，我们得在代码上进行情况分类，我们要将第一个进入的节点作为头节点，之后再开始尾插。
2. 有空头结点的链表
直接在我们通过动态内存分配建立的空头结点之后尾插即可，不过最后记得将这个空头结点 的空间释放掉。

在下面的代码中，我写的是不带空头结点的一种。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if(pHead==NULL)
            return NULL;
        
        struct ListNode* greathead=NULL;
        struct ListNode* greattail=NULL;
        
        struct ListNode* lesshead=NULL;
        struct ListNode* lesstail=NULL;
        
        struct ListNode*cur=pHead;
        
        while(cur)
        {
            if(cur->val<x)
            {
                if(lesstail==NULL)
                    lesshead=lesstail=cur;
                else
                {
                    lesstail->next=cur;
                    lesstail=cur;
                }
            }
            
           else
            {
                if(greattail==NULL)
                    greathead=greattail=cur;
                else
                {
                    greattail->next=cur;
                    greattail=cur;
                }
            }
            cur=cur->next;
            
        }
        if(greathead==NULL)
            return lesshead;
        if(lesshead==NULL)
            return greathead;
        
        greattail->next=NULL;
        lesstail->next=greathead;
        return lesshead;  
    }
};

7. 链表的回文结构。

对于回文结构的判断，有一定的难度，比较具有综合性。

具体步骤为：

1. 通过大小指针法找到中间节点
2. 从中间节点开始，将之后的节点反转（链表的反转）
3. 分别从头结点和中间节点开始遍历，如果所有的节点都对应相等，那么就符合回文结构。

这里的每一步都在之前的题目之中讲过，所以不再次赘述了。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A==NULL)
        {
            return NULL;
        }
        struct ListNode*slow=A;
        struct ListNode*fast=A;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        
        struct ListNode*a=NULL;
        struct ListNode*b=slow;
        struct ListNode*c=slow->next;
        
        while(b)
        {
              b->next=a;
              a=b;
              b=c;
              if(c)
                  c=c->next;
              
        }
        struct ListNode*cur=A;
        while(cur&&a)
        {
            if(cur->val!=a->val)
                return false;
            
            cur=cur->next;
            a=a->next;
        }
        return true;
        
        
    
    }
};

8. 输入两个链表，找出它们的第一个公共结点。

当我们看到相交的时候，可能会想到两种情况：

• 只有一部分节点相同，之后又错开
• 相交之后，之后的节点全部相同

但是，实际上，第一种情况是不可能的：

两个指针可以指向一个地址，但是，一个指针不可能指向两个地址，所以，只可能会有第二种情况。

知晓了这一点，我们就有了一个判断链表是否相交的方法：

对于两个链表，只要最后一个节点是一样的，那么就说明这两个链表一定相交

但是，这种方法不能确定相遇点，所以我们要寻找其他的方法：

我们可以依次比较对应位置的节点，如果发现相同了，那么说明在这里相交了。

但是，如果链表的长度不相等的化，我们如何进行对应位置的遍历以及比较呢？这时候又是大小指针法的应用，对于长的链表，我们使用快指针先把他们的差值先走完，这时候再启动慢指针，这时候两个链表指针就对齐了。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lenA=0;
    int lenB=0;
    struct ListNode*curA=headA;
    struct ListNode*curB=headB;


    while(curA)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB)
    {
        lenB++;
        curB=curB->next;
    }
    struct ListNode*longhead=headA;
    struct ListNode*shorthead=headB;
    if(lenA<lenB)
    {
        longhead=headB;
        shorthead=headA;
    }
    int k=abs(lenA-lenB);
    while(k--)
    {
        longhead=longhead->next;
    }
    while(longhead&&shorthead)
    {
        if(longhead==shorthead)
         return longhead;

         longhead=longhead->next;
         shorthead=shorthead->next;

    }
    return NULL;
}

9. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head;
    struct ListNode*fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode*meet=slow;
            while(head!=meet)
            {
               head=head->next;
               meet=meet->next;
            }
          return meet;
        }
        
    }
    return NULL;

    
}