【数据结构】单链表经典面试题10道及详细思路代码_cur->next = prev->next;

目录

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

2. 反转一个单链表。

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

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

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

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

7. 链表的回文结构。

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

9. 给定一个链表，判断链表中是否有环。

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

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

leetcode 203 移除链表元素

typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val){
    Node* cur = head;
    Node *prev = NULL;//保存cur的前一个结点
    while(cur)
    {
 
        if(cur->val == val)
        {
            if(NULL == prev)
            {
                //需要删除的cur刚好是链表第一个结点，此时prev是空
                //需要修改head的指向
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
                 //删除cur
                 //让prev的next指向此时cur的next
                   prev->next = cur->next;
                  free(cur);
                 //将prev赋值给cur
                  cur = prev->next;
            }
           
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

2. 反转一个单链表。

leetcode 206 反转链表

typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head){
 
    Node* prev = NULL;
    Node* cur = head;
    Node* next = NULL;
        //以左图为例子，此时，cur在1，其他在null
 
    while(cur)
    {
        next = cur->next; //next在2，cur在1，prev在空
        cur->next = prev;//改变链表指向，让cur指向空
        prev = cur; //prev在1
        cur = next;//cur在2，依次改变链表每个结点指向
    }
    return prev;
 
}

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

leetcode 876

typedef struct ListNode Node;
struct ListNode* middleNode(struct ListNode* head){
    Node* fast = head;
    Node* slow = head;
 
    //fast和接下来2步都不为空
    //fast不为null，可以保证fast第一步成功
    //fast->next 不为空，保证第二部走成功
    while(fast &&  fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
 
    return slow;
}

Node* fast = head;
    Node* slow = head;
    Node* prev =NULL;
 
    while(fast &&  fast->next)
    {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }
    if(fast)  //总数是奇数
    {
        return slow;
    }
    else  //总数是偶数
    {
        return prev;
    }

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

最优思路：先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点

OJ链接

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    //先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点
    //1.对参数进行检测
    if(NULL ==pListHead || k <= 0)
        return NULL;
    
    //2.定义两个指针
    struct ListNode* front = pListHead;
    struct ListNode* back = pListHead;
    
    //注意K可能会大于链表长度
    while(k)
    {
        if(NULL == front)
            return NULL;
        
       front = front->next;
        k--;
    }
    while(front != NULL)
    {
        front = front->next;
        back = back->next;
    }
    return back;    
}

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

（Leetcode 21.合并两个有序链表）

 思路：

1.先创建一个新的链表

2.让cur1 和 cur2遍历两个链表，遇到的节点逐个比较，将值小的节点往新链表的末尾tail进行尾插

3.上述循环结束后，要判断有无链表还有剩余元素，把剩余的元素尾插到新链表的末尾。

typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(NULL == list1)
          return list2;
 
    if(NULL == list2)
          return list1;
    //走到这里，说明两个链表均不为空,需要合并
    Node* pNewList =NULL;
    Node* cur1 = list1;
    Node* cur2 = list2;
    //在pnewlist中插入第一个节点，第一个节点要修改pnewlist的指向
    if(cur1 -> val <= cur2->val)
    {
        pNewList = cur1;
        cur1 = cur1->next;
    }
    else
    {
        pNewList = cur2;
        cur2 = cur2->next;
    }
    Node* tail = pNewList;//新链表的尾部
 
    //让cur1 和 cur2遍历两个链表，遇到的节点逐个比较
    //将值小的节点往新链表的末尾tail进行尾插
 
    while(cur1  && cur2)
    {
        if(cur1->val <= cur2->val)
        {
            tail->next = cur1;
            cur1 = cur1->next;  
        }
        else
        {
            tail->next = cur2;
            cur2 = cur2->next;
        }
         tail = tail->next;
    }
    if(cur1)
    {
        tail->next =cur1;
    }
    else if(cur2)
    {
        tail->next = cur2;
    }
    else{
        return pNewList;
    }
    return pNewList;
}

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

OJ链接

思路：

1.创建两个链表，一个链表尾插值小于x的节点，另一个链表中插值大于等于x的节点

2.遍历原链表，将链表中的节点往两个新链表中尾插--新链表最好将其给成带头节点的单链表

3.将两个链表拼接

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if(NULL == pHead)
            return pHead;
        
        //less链表中尾插小于x的节点
        ListNode less(0);
        ListNode* lessTail = &less;
        
        //尾插大于等于x的节点
        ListNode greater(0);
        ListNode* greaterTail = &greater;
        
        ListNode* cur = pHead;
        
        //利用cur去遍历phead
        while(cur)
        {
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;   
            }
            else
            {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
              cur = cur->next;
        }
        
        //拼接两个链表
        lessTail ->next = greater.next;
        greaterTail->next = NULL;
        
        return less.next; 
    }
};

7. 链表的回文结构。

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。OJ链接

思路1：

题目中条件：保证链表长度小于等于900，所以额外空间创建如下 为o(1)

1.给一个900的Int类型的数组

2.遍历链表，让每个节点的值放入数组

3.检测数组中保存的元素是否为回文结构

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        int array[900];
        
        ListNode* cur = A;
        int size = 0;
        //遍历链表
        while(cur)
        {
            array[size] = cur-> val;
            cur = cur->next;
            size++;
        }
        
        int left = 0;
        int right = size-1;
        while(left < right)
        {
            if(array[left] != array[right])
            {
                return false;
            }
            else
            {
                left++;
                right--;
            }
        }
        return true ;
    }
};

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。（去掉一个条件）

思路2：
1.找到链表的中间节点，从中间节点的位置将链表分开，形成2个链表---->找中间节点:采用快慢指针ok
2.对后半部分进行逆置---链表的逆置ok
3.将两个链表从前往后逐个节点进行比对，如果比对之后发现所有节点的值域都相同，则是回文链表，否则不是
4.将链表还原成原链表
注意:一般情况下不要破坏链表的结构，如果破坏了最后最好将其恢复

class PalindromeList {
public:
    ListNode* getMiddleNode(ListNode* plist)
    {
        ListNode* fast = plist;
        ListNode* slow = plist;
        
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }   
        ListNode* reverseList(ListNode* plist)
        {
            ListNode* cur = plist;
            ListNode* prev = NULL;
            ListNode* next = NULL;
            
            while(cur)
            {
                next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            return prev;
        }
        
        bool chkPalindrome(ListNode* A)
        {
            if(NULL == A || NULL == A->next)
                return true;
            //找到A链表中间节点，然后从中间节点的位置将其断开
            ListNode* list1 = A;
            ListNode* midNode = getMiddleNode(A);
            ListNode* list2 = midNode->next;
            midNode->next = NULL;
            
            //将后半部分进行逆置
            list2 = reverseList(list2);
            
            //将list1和list2中的节点逐个比较
            bool ret = true;
            ListNode* cur1 = list1;
            ListNode* cur2 = list2;
            
            while(cur1 && cur2)
            {
                if(cur1->val != cur2->val)
                {
                    ret = false;
                    break;
                }
                
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            //还原链表
            list2 = reverseList(list2);
            midNode->next = list2;
            
            return ret;
        }  
};

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

leetcode 160.相交链表

下面是两个节点相交的各类情况：

 在相交的情况下，求交点的方式：

1.让较长的链表先走两个链表的差值步数

2.在让两个链表同时往后走，直到遇到地址相同的交点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //参数检测，如果有一个链表为空，不可能相交
    if(NULL == headA || NULL == headB)
    {
        return NULL;
    }
    
    //1.检测headA和headB是否相交
    //分别找到两个链表最后一个节点，相同就相交，不同则不交
    struct ListNode* curA = headA;
    int sizeA = 1;
    int sizeB = 1;
    while(curA ->next)
    {
        curA = curA->next;
        sizeA++;
    }
    struct ListNode* curB = headB;
    while(curB->next)
    {
        curB = curB->next;
        sizeB++;
    }
    if(curB != curA)
          return NULL;
 
    //2.执行到此处说明相交
    int gap = sizeA - sizeB;
    curA = headA;
    curB = headB;
    if(gap > 0)
    {
        //headA长
        while (gap--)
        {
            curA =  curA->next;
        }
    }
    else
    {
        while(gap++)
        {
            curB = curB->next;
        }
    }
    while(curA != curB)
    {
        curA = curA->next;
        curB =  curB->next;
    }
    return curA;   
}

9. 给定一个链表，判断链表中是否有环。

leetcode 141，环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

思路：

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

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

leetcode 142环形链表2

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

 ​​​​​​​

struct ListNode *detectCycle(struct ListNode *head) {
 
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    int hasCycle = 0; //标记链表是否带环
 
    while(fast && fast->next)
    {
        fast= fast->next->next;
        slow = slow->next;
 
        if(fast == slow)
        {
            hasCycle = 1;
            break;
        }
    }
 
    
    if(!hasCycle)//链表不带环
        return NULL;
 
    struct ListNode* pH = head;
    struct ListNode* pM = fast;  //相遇点
    while(pH != pM)
    {
        pH = pH->next;
        pM = pM->next;
    }
    return pM;    
}