频率最高的手写代码面试题--链表类型(上)

红太狼 2023-07-06 04:51 87阅读 0赞

### 链表笔试 or 面试题 ###

*   *   *  1、奇偶链表
         *  2、删除链表中的节点
         *  3、移除链表元素
         *  4、相交链表
         *  5、复制链表
         *  6、环形链表
         *  7、重排链表
         *  8、对链表进行排序
         *  9、删除排序链表中的重复元素
         *  10、删除排序链表中的重复元素 II

### 1、奇偶链表 ###

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数

> 示例1  
> 输入: 1->2->3->4->5->NULL  
> 输出: 1->3->5->2->4->NULL

> 示例2  
> 输入: 2->1->3->5->6->4->7->NULL  
> 输出: 2->3->6->7->1->5->4->NULL

错误思路：两个指针连接在一起，最后隔一个删除节点，很明显这种思路失败了！

因为如果尾节点直接指向头指针，这样会造成循环链表，导致无法退出循环.

如果不考虑空间复杂度，复制一个一样的指针，这种思路其实也是可以的.但题目要求空间复杂度为O（1），案例中一个链表如果有很多个节点，那么就都需要复制，这显然是很不ok的解法

**更好的思路**：定义两个指针，一个是奇数指针，一个是偶数指针，两个指针螺旋式地解开链表

def oddEvenList(self, head: ListNode) -> ListNode:
            if not head:
                return head
            even = head.next
            odd = head
            head_even = even
            while odd.next and even.next:
                odd.next = even.next
                odd = even.next
    
                even.next = odd.next
                even = odd.next
            odd.next = head_even
            return head

### 2、删除链表中的节点 ###

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点

> 现有一个链表 – head = \[4,5,1,9\]，它可以表示为:  
> ![">][20191218192236948.png]  
> 示例 1:  
> 输入: head = \[4,5,1,9\], node = 5  
> 输出: \[4,1,9\]  
> 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

> 示例 2:  
> 输入: head = \[4,5,1,9\], node = 1  
> 输出: \[4,5,9\]  
> 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:  
链表至少包含两个节点。  
链表中所有节点的值都是唯一的。  
给定的节点为非末尾节点并且一定是链表中的一个有效节点。  
不要从你的函数中返回任何结果。

方法一：通过遍历，找到 node 的上一个节点，时间复杂度为O(N)

ListNode* deleteNode(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            ListNode* res = head;
            if(head->val==val){ 
                return head->next;
            }
            while(head && head->next){ 
                if(head->next->val == val){ 
                    head->next = head->next->next;
                }
                head = head->next;
            }
            return res;
        }

方法二：递归写法

ListNode* deleteNode(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            if(head->val == val){ 
                return head->next;
            }
            head->next = deleteNode(head->next,val);
            return head;
        }

方法三：使用 O(1) 的时间复杂度完成操作. 但是需要注意的是，如果可以确定 node 不是最后一个节点，这种方法是可行的，但是如果是最后一个节点，无法删除通过 node = None 的方式删除节点

def deleteNode(self, node):
    	if node.next:
    		node.val = node.next.val
    	    node.next = node.next.next
    	else:
    		node = None

### 3、移除链表元素 ###

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

> 示例  
> 输入: 1->2->6->3->4->5->6, val = 6  
> 输出: 1->2->3->4->5

方法一：**先申请出一个节点**，然后进行连接判断操作

ListNode* removeElements(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            ListNode* dumpy = new ListNode(-1);
            dumpy->next = head;
            ListNode* cur = dumpy;
            while(head){ 
                if(head->val != val){ 
                    cur->next = head;
                    cur = cur->next;
                }
                head = head->next;
            }
            cur->next = nullptr;
            return dumpy->next;
        }

当然写法不唯一，但大致思路都是一样的

ListNode* removeElements(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            ListNode* dumpy = new ListNode(-1);
            dumpy->next = head;
            ListNode* cur = dumpy;
            while(head){ 
                if(head->val==val){ 
                    cur->next = head->next;
                }else{ 
                    cur = head;
                }
                head = head->next;
            }
            return dumpy->next;
        }

方法二：递归版本

ListNode* removeElements(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            // 先一口气走到链表的尾部
            head->next = removeElements(head->next,val);
            if(head->val == val){ 
                // 如果相等了，则删除head节点
                return head->next;
            }else{ 
            	// 返回 head
                return head;
            }
        }

方法三：直接跳过第一个节点，从第二个节点开始判断，如果相等则处理方式和方法一相同，最后判断第一个节点是否应该要删除

ListNode* removeElements(ListNode* head, int val) { 
            if(head == nullptr){ 
                return head;
            }
            ListNode* dumpy = head;
            while(dumpy->next){ 
                if(dumpy->next->val==val){ 
                    dumpy->next = dumpy->next->next;
                }else{ 
                    dumpy = dumpy->next;
                }
            }
            return head->val == val?head->next:head;
        }

### 4、相交链表 ###

编写一个程序，找到两个单链表相交的起始节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70][]

解题思路：连接两个链表，那该怎么连接？ 我们让 A 链表遍历，直到为空的时候，然后把 B 链表赋值给 A 链表，与此同时，当 B 链表遍历为空的时候，把 A 链表赋值给 B 链表，这样就相等于连接起来了。

def getIntersectionNode(headA, headB) :
            if not headB or not headA:
                return None
            ha,hb = headA,headB
            while ha!=hb:
                ha = ha.next if ha else headB
                hb = hb.next if hb else headA
            return ha

### 5、复制链表 ###

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70 1]

思路：分三步骤，复制 next 指针，复制 random 指针，再拆开链表

Node* copyRandomList(Node* head) { 
            if(head == nullptr){ 
                return head;
            }
            // 链表节点的复制
            Node* cur = head;
            while(cur){ 
                Node* node = new Node(cur->val);
                node->next = cur->next;
                cur->next = node;
                cur = cur->next->next;
            }
            // 随机指针的复制
            cur = head;
            while(cur){ 
                if(cur->random){ 
                    cur->next->random = cur->random->next;
                }
                cur = cur->next->next;
            }
            // 拆开链表
            Node* CopyHead = head->next;
            Node* CurCopy = CopyHead;
            cur = head;
            while(cur){ 
                cur->next = cur->next->next;
                cur = cur->next;
    
                if(CurCopy->next){ 
                    CurCopy->next = CurCopy->next->next;
                    CurCopy = CurCopy->next;
                }
            }
            return CopyHead;
        }

### 6、环形链表 ###

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环

思路：思路比较简单，就是一个快慢指针的方法，如果两个指针相遇就确定有环，但在一些特别短的链表要稍微注意一点，可能会非法访问。

def hasCycle(self, head: ListNode) -> bool:
            if not head or not head.next:
                return False
            low = head
            fast = head.next
            while low and fast:
                if low.val==fast.val:
                    return True
                low = low.next
                fast = fast.next
                if fast:
                    fast = fast.next
            return False

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

**说明：不允许修改给定的链表。**

思路：这里用到一个特别小的数学知识

> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70 2]  
> 假如两个指针在 f 点相遇，快指针走的路程是 a-b-c-d-e-f-g-c-d-e  
> ，慢指针走的时候 a-b-c-d-e ,快指针多走了一圈，但是他们所用的时间是一样的 设为 t;设快指针走的速度为 2v,慢指针走的速度为 v,设环的周长为 s ，那么可以得出 2vt -vt == s（快指针比慢指针多走了一圈的路径）所以 vt == s;由于 vt ==s得出慢指针走的路径就是环一圈的周长，也就是说，从a到e 就等于 c-d-e-f-g,那么就可以得出相遇的节点到环的入口点就是链表的起点到环的入口点。

所以第一步：先确定有环没，如果没有返回 none，如果有则记录下两个指针相遇节点。

第二步：从相遇节点到和链表起点再次相遇的时候，就是环的入口点。

def detectCycle(self, head: ListNode) -> ListNode:
            if not head or not head.next:
                return None
            cur = head
            low = head.next
            fast = head.next.next
            temp = None
            while low and fast:
            	# 比较节点的时候尽量不要比较他们的值，而是比较地址
            	# 如果写成 low.val == fast.val 有可能是错误的
                if low == fast:
                    temp = low
                    break
                low = low.next
                fast = fast.next
                if fast:
                    fast = fast.next
            if not temp:
                return temp
            while temp and cur:
                if temp == cur:
                    return temp
                temp = temp.next
                cur = cur.next

代码优化版本…

def detectCycle(self, head: ListNode) -> ListNode:
            if not head or not head.next:
                return None
            cur = fast = low = head
            while fast and fast.next:
                low = low.next
                fast = fast.next.next
                if low == fast:
                    while cur != fast:
                        cur = cur.next
                        fast = fast.next
                    return cur
            return None

### 7、重排链表 ###

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，  
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

> 示例1  
> 给定链表 1->2->3->4, 重新排列为 1->4->2->3.

> 示例2  
> 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

思路：先利用快慢指针知道中间的值，把中间的下一个节点到末尾节点之前所有的节点保存到列表中，然后把中间节点的下一个节点置位空。最后用列表里的节点对链表的进行间隔插入。

def reorderList(self, head: ListNode) -> None:
            if not head or not head.next:
                return
            cut = fast = slow = head
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
            cur_next = slow.next
            slow.next = None
            temp = []
            while cur_next:
                temp.append(cur_next)
                if cur_next:
                    cur_next = cur_next.next
            while temp:
                node = temp.pop(-1)
                node.next = cut.next
                cut.next = node
                cut = node.next

### 8、对链表进行排序 ###

方法一：对链表进行插入排序

![Insertion-sort-example-300px.gif][]

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）  
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。  
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。  
重复直到所有输入数据插入完为止。

> 示例 1：  
> 输入: 4->2->1->3  
> 输出: 1->2->3->4

> 示例 2：  
> 输入: -1->5->3->4->0  
> 输出: -1->0->3->4->5

C++ 参考代码

ListNode* InserSort(ListNode* head) { 
    	if (head == nullptr || head->next == nullptr) { 
    		return head;
    	}
    	ListNode* dummpy = new ListNode(0);
    	dummpy->next = head;
    	while (head && head->next) { 
    		if (head->_val <= head->next->_val) { 
    			head = head->next;
    			continue;
    		}
    		ListNode* pre = dummpy;
    		while (pre->next->_val < head->next->_val) { 
    			pre = pre->next;
    		}
    		// 将head 的下一个节点进行保存
    		ListNode* headNext = head->next;
    		head->next = headNext->next;
    		headNext->next = pre->next;
    		pre->next = headNext;
    	}
    	return dummpy->next;
    }

缺点：时间复杂度为O(N2)

方法二：利用快速排序，选取一个基准值，将链表划分为两部分，左边都比基准值小，右边都比基准值大，然后递归进行

// 快速排序
    ListNode* partition(ListNode* start, ListNode* end) { 
    	ListNode* left = start;
    	ListNode* right = start;
    	while (right != end) { 
    		if (right->_val < start->_val) { 
    			left = left->next;
    			swap(left->_val, right->_val);
    		}
    		right = right->next;
    	}
    	swap(start->_val, left->_val);
    	return left;
    }
    
    void quick_sort(ListNode* left,ListNode* right) { 
    	if (left != right) { 
    		ListNode* index = partition(left, right);
    		quick_sort(left, index);
    		quick_sort(index->next, right);
    	}
    }
    
    void List(ListNode* head) { 
    	if (head == nullptr || head->next == nullptr) { 
    		return;
    	}
    	quick_sort(head,nullptr);
    }

方法三：归并排序

通过递归的方式将链表分为两部分，对左边再次进行分割，右边也是一样，到不能分割的时候，对两个链表进行合并为个有序链表，返回有序链表的头指针

// 归并排序
    ListNode* merage_list(ListNode* l1, ListNode* l2) { 
    	ListNode* head = new ListNode(0);
    	ListNode* p = head;
    	while (l1 && l2) { 
    		if (l1->_val <= l2->_val) { 
    			p->next = l1;
    			l1 = l1->next;
    		}
    		else { 
    			p->next = l2;
    			l2 = l2->next;
    		}
    		p = p->next;
    	}
    	p->next = l1 ? l1 : l2;
    	return head->next;
    }
    
    ListNode* sortList(ListNode* head) { 
    	if (head != nullptr || head->next != nullptr) { 
    		return head;
    	}
    	ListNode* dupmy = new ListNode(0);
    	dupmy->next = head;
    	ListNode* fast = dupmy;
    	ListNode* low = dupmy;
    	while (fast && fast->next) { 
    		fast = fast->next->next;
    		low = low->next;
    	}
    	ListNode* right = low->next;
    	low->next = nullptr;
    	return merage_list(sortList(head), sortList(right));
    }

### 9、删除排序链表中的重复元素 ###

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

> 示例1  
> 输入: 1->1->2  
> 输出: 1->2

> 示例2  
> 输入: 1->1->2->3->3  
> 输出: 1->2->3

思路：定义两个指针，如果两个指针的值不相等则各自往前走，如果相等的话，则把前一个指针的next指向后一个指针的next，这样就可以保证重复的指针只留下一个。

一次性通过，没有调试（偷偷高兴）！

def deleteDuplicates(self, head: ListNode) -> ListNode:
            if not head:
                return None
            cur = head
            ret = cur
            next_node = head.next
            while next_node != None:
                if cur.val != next_node.val:
                    cur = next_node
                else:
                    cur.next = next_node.next
                next_node = next_node.next
            return ret

当然也可以不用设置两个指针那么麻烦，直接这样

if not head: return head
        dummy = head
        while head.next:
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
        return dummy

还可以利用递归的方法写，稍微有点不太好理解

def deleteDuplicates(self, head: ListNode) -> ListNode:
            if head==None or head.next == None:
                return head
            head.next = self.deleteDuplicates(head.next)
            if head.val == head.next.val:
                head= head.next
            return head

递归的思想其实和循环正好是相反的，循环是从前往后删除，而递归是从后往前删除，先一口气走到尾端，然后再判断两个节点是不是相等的，如果相等，则跳过去.

当然了，如果给定链表是未排序的，这个时候就不能直接判断了，可以借助一个辅助空间去判断要不要删除当前节点

比如 1->2->3->2->3->1->5，只保留一个就行了

输出 1->2->3->5 (不一定要有序，但要保证相对顺序)

class Solution { 
    public:
        ListNode* removeDuplicateNodes(ListNode* head) { 
            if(head == nullptr){ 
                return head;
            }
            unordered_map<int,int>mp;
            ListNode* p = head;
            mp[p->val] +=1;
            while(p != nullptr){ 
                while(p->next && mp[p->next->val] != 0){ 
                    p->next = p->next->next;
                }
                if(p->next){ 
                    mp[p->next->val]++;
                }
            }
            return head;
        }
    };

其他思路：首先要进行排序，然后就可以进行去重

### 10、删除排序链表中的重复元素 II ###

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

> 示例1  
> 输入: 1->2->3->3->4->4->5  
> 输出: 1->2->5

> 示例2  
> 输入: 1->1->1->2->3  
> 输出: 2->3

这道题和上一道题不同之处就在于：开头不好处理，如果第一个结点就重复的话很难处理，而且要删除，那么就没有头结点了，所以重新定义一个头结点。

def deleteDuplicates(self, head: ListNode) -> ListNode:
            if head==None or head.next == None:
                return head
            dummy = pre = ListNode(0)
            dummy.next = head
            while head and head.next:
                if head.val == head.next.val:
                    while head.next and head.val==head.next.val:
                        head = head.next
                    pre.next = head.next
                else:
                    pre = pre.next
                head = head.next
            return dummy.next

[20191218192236948.png]: https://img-blog.csdnimg.cn/20191218192236948.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030810285945.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200308102917940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191205121104428.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70
[Insertion-sort-example-300px.gif]: https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif