C语言单链表面试题详解

第一题：力扣移除链表元素：力扣链接：力扣

我解此题的思路是碰见要移除的链表元素就释放然后让前一个节点链接后一个节点 。代码如图所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
        if (head==NULL)
        {
            return NULL;
        }
        struct ListNode*cur = head;
        struct ListNode*tmp = NULL;
        while (cur)
        {
            if (head->val==val)
            {
                  cur = cur->next;
                  free(head);
                  head = cur;
            }
            else
            {
                if (cur->val!=val)
                {
                    tmp = cur;
                    cur = cur->next;
                }
                else
                {
                    tmp->next=cur->next;
                    free(cur);
                    cur = tmp->next;
                }
            }
        }
        
        return head;
}

 

 我们先创建两个指针，一个用来遍历链表一个用来记录要删除节点的上一个节点，然后如图一样，我们要先确定要删除的节点是否是第一个节点，如果是第一个节点则用cur保存下一个节点的地址然后释放头结点再将cur给头结点。如果第一个节点不是要删除的节点就按我们的思路，一个指针往后遍历一个指针记录前一个节点的地址，当遇到要删除的节点时，先将要删除的节点的后一个节点的地址给要删除的节点的前一个节点的next，然后释放要删除的节点，再将要删除的节点的下一个节点的地址给遍历的指针cur。当我们提交代码时发现有一个空指针的测试用例不通过，这时候只需要在最开始判断这个链表是否为空指针，如果一开始就是空指针则不需要任何操作直接返回空指针即可。

第二题：反转链表 力扣链接：力扣

反转链表就是将1->2->3->NULL反转变为3->2->1->NULL,要怎么实现呢？我们看图：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
       if (head==NULL)
       {
           return NULL;
       }
       struct ListNode*n1 = NULL;
       struct ListNode*n2 = head;
       struct ListNode*n3 = head->next;
       while (n2!=NULL)
       {
           n2->next = n1;
           n1 = n2;
           n2 = n3;
           if (n3!=NULL)
           {
               n3 = n3->next;
           }
       }
       return n1;
}

 如图所示，我们创建三个指针为n1，n2，n3，n1为空指针，n2为头结点，n3为头结点的下一个节点，当n2不等于空指针进入循环，让n2指向n1，然后让n1走到n2的位置，n2走到n3的位置，n3往后走一步，由示意图看出n3为空时反转并没有停止所以需要判断n3是否为空才往后走，否则会对空指针解引用，反转到最后的头结点变为n1所以返回n1即可。

第三题：链表的中间节点 力扣链接：力扣

返回链表的中间节点就需要看链表是奇数还是偶数，如果是奇数则是中间，如果是偶数则有两个中间节点题目说是第二个中间节点 。第一种解法：走完整个链表算出链表的所有节点数，然后除2得到走向中间节点的步数，这个方法偶数正好是第二个节点下面我们实现一下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
        struct ListNode*cur = head;
        int count = 0;
        while (cur)
        {
            count++;
            cur = cur->next;
        }
        count = count/2;
        cur = head;
        while (count--)
        {
             cur = cur->next;
        }
        return cur;
}

首先用cur去遍历链表，然后定义变量count计算链表中节点的个数，然后cur每进循环一次count++一次，算出节点的个数后再让cur指向头结点，while (count--)和while(--count)并不一样，如果次数是2count--会进入循环2次，而--count只进入一次，原因是前置减减先减减在使用，后置--先使用再减减。

第二种方法是快慢指针的方法，快慢指针的方法大家一定要学会，在单链表中很多题都可以用快慢指针来解决。如图所示：

我们发现当节点为偶数时当快指针指向空时慢指针刚好为中间节点，那如果是奇数呢？看图：

我们发现当节点数为奇数时，快指针的next为NULL时慢指针指向中间节点，所以代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
        struct ListNode*slow = head;
        struct ListNode*fast = head;
        while (fast&&fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
}

 如图所示循环条件是快指针不为NULL并且快指针的next不为NULL，可以看出快慢指针相比于刚刚第一种解法的优势，快慢指针的时间复杂度一定是比第一种解法快的。

第四题：链表中倒数第K个结点 牛客网链接：链表中倒数第k个结点_牛客题霸_牛客网

求一个链表中倒数第几个结点，我们需要考虑几种情况，第一种情况当链表为空时我们直接返回空指针，第二种情况当k大于链表的长度是返回的是空指针，第三种情况当指针走到空指针而k还没有减为0时这时候指针继续走只会对空指针进行解引用。如图所示：

如图所示当是正常情况时我们先让快指针走K步，然后两个指针一起走当快指针指向NULL时慢指针就是倒数第K个节点，如果K大于节点的长度我们就要返回NULL，所以我们需要一个变量计算链表的长度，代码如下：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if (pListHead==NULL)
    {
        return NULL;
    }
    struct ListNode*fast = pListHead;
    struct ListNode*slow = pListHead;
    int count = 0;
    int t = k;
    while (t--)
    {
        count++;
        fast = fast->next;
        if (fast==NULL)
        {
            break;
        }
    }
    if (k>count)
    {
        return NULL;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

 进来的时候先判断链表是否为NULL，如果为空则返回NULL，这里为什么要把k的值赋给t呢，原因是如果用k--的话下面判断k是否大于链表长度的时候就会出错，k自减后已经不是原先的值了还怎么与链表长度相比呢，所以这样用t，当快指针为空说明链表走完了直接退出循环，当k<链表长度时一起走即可否则就返回空指针。

第五题：合并两个有序链表 力扣链接：力扣

合并两个有序链表很简单，用两个指针一个指向第一个链表一个指向第二个链表，然后再开辟一个新的头结点，让两个指针指向的节点的值进行比较，小的就连在新开辟的头结点的后面，当有一个链表走完时再将另一个链表的节点放入新节点后面，如图所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     if (list1==NULL)
     {
         return list2;
     }
     if (list2==NULL)
     {
         return list1;
     }
      struct ListNode*n1 = list1;
      struct ListNode*n2 = list2;
      struct ListNode*n3 = NULL;
      struct ListNode*newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
      if (n1->val>n2->val)
      {
          newnode->next = n2;
          n3 = n2;
          n2 = n2->next;

      }
      else
      {
          newnode->next = n1;
          n3 = n1;
          n1 = n1->next;
      }
      while (n1&&n2)
      {
          if (n1->val<n2->val)
          {
              n3->next = n1;
              n3 = n1;
              n1 = n1->next;
          }
          else
          {
              n3->next = n2;
              n3 = n2;
              n2 = n2->next;
          }
      }
      while (n1)
      {
          n3->next = n1;
          n3 = n1;
          n1 = n1->next;
      }
      while (n2)
      {
          n3->next = n2;
          n3 = n2;
          n2 = n2->next;
      }
      n3->next = NULL;
      struct ListNode*rehead = newnode->next;
      free(newnode);
      return rehead;
}

 这道题开辟头结点显得有些麻烦，下面我们用不开辟头结点的方法试试

第二种方法可以不用开辟头指针，由于是两个链表所以一开始就判断哪一个链表的第一个节点的值小，然后将这个节点直接给待会要返回的新节点。

 

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
     if (list1==NULL)
     {
         return list2;
     }
     if (list2==NULL)
     {
         return list1;
     }
      struct ListNode*n1 = list1;
      struct ListNode*n2 = list2;
      struct ListNode*n3 = NULL;
      if (n1->val>n2->val)
      {
          n3 = n2;
          n2 = n2->next;
      }
      else
      {
          n3 = n1;
          n1 = n1->next;
      }
      struct ListNode*newnode = n3;
      while (n1&&n2)
      {
          if (n1->val<n2->val)
          {
              n3->next = n1;
              n3 = n1;
              n1 = n1->next;
          }
          else
          {
              n3->next = n2;
              n3 = n2;
              n2 = n2->next;
          }
      }
      while (n1)
      {
          n3->next = n1;
          n3 = n1;
          n1 = n1->next;
      }
      while (n2)
      {
          n3->next = n2;
          n3 = n2;
          n2 = n2->next;
      }
      n3->next = NULL;
      return newnode;
}

 我们先确认一个小的节点让n3等于这个小节点然后开始从这个节点的后面链接，当n1和n2都不为空的时候进入循环，如果有一个为空了就退出循环，接下来看是哪个链表结束了，将没结束的链表连接到n3->next的后面，通过画图我们发现当所有节点链接完后最后是没有空指针的所有我们给新链表最后加上空指针，由于这个时候n3已经不指向新节点的第一个节点了，所有我在刚给n3分配第一个小的节点的时候用newnode指向n3，最后返回n3即可。

第六题：链表分割 牛客网链接：链表分割_牛客题霸_牛客网

这道题什么意思呢？就是将链表中小于x的节点放在其他节点之前并且相对顺序不变，看图：

 

我们的思路是先开辟两个头节点，用一个指针去遍历链表，如果遇到小于x的节点就放在第一个头结点的后面，相反则放到第二个头结点的后面，放完后直接将小节点链表的最后一个节点链接在大节点链表的前面，最后有一个非常重要的问题，当最后一个节点指向其他节点时会造成死循环，所以我们要将链接起来的链表最后一个节点的next置为空。思路如图：

 

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode*small = (ListNode*)malloc(sizeof(struct ListNode));
        ListNode*big = (ListNode*)malloc(sizeof(struct ListNode));
        ListNode*cur = pHead;
        ListNode*tmp1 = small;
        ListNode*tmp2 = big;
        while (cur)
        {
            if (cur->val<x)
            {
                tmp1->next = cur;
                tmp1 = cur;
                cur = cur->next;
            }
            else
            {
                tmp2->next = cur;
                tmp2 = cur;
                cur = cur->next;
            }
        }
        if (small->next == NULL)
        {
           return big->next;
        }
        if (big->next==NULL)
        {
            return small->next;
        }
        tmp1->next = big->next;
        tmp2->next = NULL;
        ListNode*rehead = small->next;
        free(small);
        free(big);
        return rehead;
    }
};

 在这里我们先开辟了两个头节点，并且分别为两个头节点创建了两个移动的指针tmp1和tmp2，这样方便在移元素的时候每次都能链接在尾部，我们在链接大节点链表和小节点链表之前判断了大小节点链表是否分别为NULL，原因是当链表中所有元素都小于x时，那么只需要返回小节点链表即可，当链表中所有元素都大于x时，只需要返回大节点链表，我们在返回的时候一定要记得释放开辟的头结点否则会造成内存泄漏，如果链表中最后一个节点为大节点那么新链表最后是NULL，如果链表中最后一个节点为小节点那么新链表最后还连接其他值就会造成死循环，所以需要将最后一个链表节点的next置为NULL。

第七题：链表的回文结构 牛客网链接：链表的回文结构_牛客题霸_牛客网

从题目描述我们可以看到链表的回文就是中间链表和从头结点开始到中间链表每个值相等即可。那么我们可以想到前面做过的两道题，一个是求链表的中间节点一个是反转链表，我们的思想是找到链表的中间节点然后开始反转链表，用反转后的链表和从链表头结点开始一个一个比较值，如图所示：

 

接下来我们实现代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
          ListNode*fast = A;
          ListNode*slow = A;
          while (fast&&fast->next)
          {
              fast = fast->next->next;
              slow = slow->next;
          }
          ListNode*n2 = slow;
          ListNode*n1 = NULL;
          ListNode*n3 = slow->next;
          while (n2)
          {
              n2->next = n1;
              n1 = n2;
              n2 = n3;
              if (n3)
              {
                  n3 = n3->next;
              }
          }
       
          while (n1)
          {
              if (n1->val!=A->val)
              {
                  return false;
              }
              n1 = n1->next;
              A = A->next;
          }
          return true;
    }
};

 在实现完代码后我们可以看一下空间复杂度，快慢指针是O（N），链表反转为为O（N），判断是否相等也为O（N），一共为O（3N）也就是O（N），而空间复杂度是O（1），因为只开辟了常数个指针变量。

第八题：相交链表 力扣链接：力扣

找链表相交的那个节点很简单，当两个链表在相交节点前走的步数相同一起走只要两个节点相同就找到了相交的起始节点， 而题目中很明显有长度不一样的，长度不一样怎么办呢？很简单，只需要让长的那个链表先走比短的多出来的几步，然后两个一起走即可。如图：

思路出来了我们就实现代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode*cur1 = headA;
    struct ListNode*cur2 = headB;
    int count1 = 0;
    int count2 = 0;
    while (cur1->next)
    {
        count1++;
        cur1 = cur1->next;
    }
    while (cur2->next)
    {
        count2++;
        cur2 = cur2->next;
    }
    if (cur1!=cur2)
    {
        return NULL;
    }
    int k = abs(count1-count2);
    struct ListNode*longlist = headA;
    struct ListNode*shortlist = headB;
    if (count1<count2)
    {
         longlist = headB;
         shortlist = headA;
    }
    while (k--)
    {
        longlist = longlist->next;
    }
    while (longlist!=shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
}

 我们用cur1去遍历第一个链表，用count1计算第一个链表的长度，然后以相同的方法计算第二个，这里可能有人会问问什么循环条件是cur->next而不是cur，原因是相交链表一旦相交则最后一个节点一定相等，所以我们用cur->next在出循环的时候 直接就是最后一个节点，如果是cur判断循环条件那么出循环的时候是NULL。我们用K接收两个链表相差多少步，abs是求绝对值的意思，然后我们创建两个变量，一个是长链表的遍历指针一个是短链表的遍历指针，我们假设A链表就是长链表，如果不是我们再让长链表为B链表，然后让长链表指针走k步，然后两个链表指针一起走当相等的时候走出循环然后返回任意一个链表即可。

第九题：环形链表 力扣链接：力扣

要判断一个链表是否为环形链表，我们需要证明一下，这里我们用到的方法是快慢指针的方法。

 

所以要判断是否是带环链表只需要判断快指针能否等于慢指针即可。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while (fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast==slow)
        {
            return true;
        }
    }
    return false;
}

 第十题：返回链表开始入环的第一个节点 力扣链接：力扣

 找到链表入环的第一个节点有两种方法，第一种证明，第二种是将环中相遇点的下一个节点记录下来，让相遇点的next为NULL，然后用相交链表的办法找到相交的那个节点并且返回。

如图第一种方法：

代码实现如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while (fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast==slow)
        {
            //找到相遇点
            struct ListNode*miss = slow;
            while (head!=miss)
            {
                head = head->next;
                miss = miss->next;
            }
            return miss;
        }
    }
    return NULL;
}

 当我们找到相遇点的时候随便将slow或者fast给miss指针，如果miss不等于head就进入循环，让两个指针同时往后走，当退出循环的时候就证明找到入环点了，返回入环点即可，如果不是环形链表则会返回空指针。

第二种方法实现思路：

 代码如下，在这里我们使用刚刚链表相交的代码即可：

 struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;
    int count1 = 0;
    int count2 = 0;
    while (cur1->next)
    {
        count1++;
        cur1 = cur1->next;
    }
    while (cur2->next)
    {
        count2++;
        cur2 = cur2->next;
    }
    if (cur1 != cur2)
    {
        return NULL;
    }
    int k = abs(count1 - count2);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (count1 < count2)
    {
        longlist = headB;
        shortlist = headA;
    }
    while (k--)
    {
        longlist = longlist->next;
    }
    while (longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    while (fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast==slow)
        {
            //找到相遇点
            struct ListNode*middle = slow;
            struct ListNode*cur = slow->next;
            slow->next = NULL;
            struct ListNode*first = getIntersectionNode(head,cur);
            return first;
        }
    }
    return NULL;
}

用cur记录相遇点的下一个节点，然后将相遇点的next置为NULL，用first接收相交链表的返回值最后返回即可。

第十一题：复杂链表的复制 力扣链接：力扣

 

本题的难点在于随机指针的复制，因为我们并不知道随机指针指向前还是指向后，这个时候该怎么办呢？首先，在原链表的每一个节点后面开辟一个一模一样的新节点，而这时候新节点的random 就等于原先节点的random的next。这里可能有人会问为什么不直接把旧节点的random给新节点的random呢？我们可以看此题的描述，是要深拷贝，如果像刚才那样就是新节点指向旧节点了就不是深拷贝了，只有让新节点的random指向新节点的random才可以。

思路屡清楚后我们来实现代码：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    if (head==NULL)
    {
        return NULL;
    }
    struct Node*cur = head;
    struct Node*next = head->next;
    while (cur)
    {
        struct Node*copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = NULL;
        cur->next = copy;
        copy->next = next;
        cur = next;
        if (next)
        {
            next = next->next;
        }
    }
    cur = head;
    next = head->next->next;
    struct ListNode*newlist = cur->next;
    while (cur)
    {
        if (cur->random==NULL)
        {
            cur->next->random = NULL;
        }
        else
        {
            cur->next->random = cur->random->next;
        }
        cur = next;
        if (next)
        {
            next = next->next->next;
        }
    }
    cur = head;
    next = head->next->next;
    while (next)
    {
        cur->next->next = next->next;
        cur->next = next;
        cur = next;
        next = next->next->next;
    }
    return newlist;
}

 第一步我们先判断链表为空的情况，当链表为空时直接返回空指针。用cur遍历链表，next指针记录cur下一个节点的地址，第一步是将每个节点后面拷贝一个相同的新节点，通过画图我们得知当cur等于空指针时将所以节点开辟完毕并且连接好，我们开辟的copy节点需要将cur的值给copy，然后将复制节点的地址给cur->next，然后next的地址给copy->next，这样就将节点连接成功了在最后要注意next为空时不可再往后走，否则会对空指针进行解引用。然后我们走第二步将random相应链接，我们将cur和next相应复位，将random链接的循环条件与第一步相同，都是cur不等于空指针，当旧节点的random为空时让新节点的random也为空，否则就是让新节点的random指向旧节点的random的next。同样为了防止next对空指针进行解应用所以判断next是否为空。接下来进行第三步重新链接链表将两个链表分开并且不改变原来链表结构，cur->next->next = next->next这句代码的意思是将新节点的第二个节点的地址给新节点的第一个节点的next，cur->next = next的意思是将旧节点的第二个节点的地址给旧节点第一个节点的next，通过画图我们得知当next为空时两个链表链接完成。最后返回在前面我们用newlist记录了新节点第一个节点的地址，然后返回newlist即可。