《iOS面试题整理》 - 链表

2019-01-22 本文已影响6人小木头

链表和数组的区别

数组
数组需要一块连续的内存空间来存储, 对内存要求比较高

链表
通过指针, 将一组零散的内存块串联起来使用

链表类型

单链表、双向链表、循环链表、双向循环链表

链表和数组的优缺点

时间复杂度
数组插入删除操作时间复杂度是 O(n)
链表插入删除操作时间复杂度是 O(1)

随机访问第 k 个元素
数组 : O(1)
链表: O(n)

链表使用场景分析

删除操作

删除节点中“值等于某个给定值”的节点
为了能找到节点, 都需要从头遍历, 尽管删除的时间复杂度是 O(1), 但是遍历查找的时间是主要的耗时点, 对应的时间复杂度为O(n)
删除特定的节点
对于单链表来说, 需要找到前驱节点, 需要重头遍历 , 时间复杂度是 O(n)
对于双向链表, 已经保存前驱节点, 时间复杂度是 O(1)

插入操作
指定节点前面插入一个节点

单链表, 时间复杂度O(n)
双向链表 O(1)

查询
对于一个有序链表, 双向链表的按值查询的效率回比单链表高, 可以记录上次查找的位置p, 每次查询时, 根据查找的值和p的大小关系, 决定是往前还是往后查找, 平均只需要查找一半的数据

性能分析

数组简单易用, 使用连续的内存空间,可以借助 CPU 的缓存机制, 预读数组中的数据, 访问效率更高。
链表在内存中不连续, 对 CPU 缓存不友好

数组的确定是大小固定, 一经声明就要占用整块连续的内存空间。如果声明数组过大, 导致系统没有足够的连续内存空间分配给它, 导致“内存不足”. 声明数组过小, 可能出现不够用的情况, 只能再申请更大的内存空间, 把原始数组拷贝过去, 非常耗时。
链表本身没有限制, 天然支持动态扩容

如果代码对内存的使用非常苛刻, 数组更合适, 链表中的每个节点都需要消耗额外的存储空间存储下一个节点的指针。对链表进行频繁的插入、删除操作还会导致内存频繁的申请和释放, 容易造成内存碎片。如果是 Java 语言, 可能导致 GC

技巧

插入节点需要注意操作顺序, 删除节点需要记得手动释放内存空间
利用哨兵, 简化链表的插入、删除操作
边界值处理
- 链表为空
- 只有一个节点
- 两个节点
- 处理头节点和尾节点

练习

从尾到头打印链表
思路:
如果可以改变链表结构的话, 翻转链表后重头打印。
利用栈先进后出的性质, 把链表所有数据压栈, 然后按照栈的弹出顺序打印。
既然可以用栈, 那么递归的本质也是一个栈结构, 用递归也是可以打印的。

// 利用栈
void print(ListNode *head) {
   
   Stack *stack = Stack new();
   
   ListNode *node = head;
   while (node ! = NULL) {
       stack.push(node);
       node = node -> next;
   }
   
   while (!stack.empty()) {
       node = stack.top();
       print(" %d\t", node -> value);
       stack.pop();
   }
}

// 递归
void recursivePrint(List *head) {
   
   if (head == NULL) return;
   
   if (head -> next != NULL) {
       recursivePrint(head -> next);
   }
   
   printf("%d \t", head -> value);
}

删除单链表指定节点, 时间复杂度 O(1)

思路：

常规方法, 遍历所有节点, 找到指定节点的前驱节点 p , 即 p -> next = target ，然后 p -> next = target -> next, 这种操作时间复杂度是O(n)
特殊操作: 把要删除的节点 p 的下一个节点 q 的值赋值给p, 再把 p 的 next 指针指向 q 的下一个节点

对于 n -1 个非尾节点, 可以在O(1) 时间内把下一个节点的内存复制到要删除的节点, 并删除下一个节点, 对于尾节点而言, 任然需要顺序查找 O(n), 总的平均时间复杂度是 [(n-1)O(1) + O(n) ] / n, 结果还是O(1)

  void deleteNode(ListNode *head, ListNode *deleteNode) {
    
    if (head == NULL || deleteNode == NULL) return ;
    
    
    if (deleteNode -> next != NULL) {
        // 删除的节点不是尾节点
        ListNode *temp = deleteNode -> next;
        deleteNode -> value = temp -> value;
        deleteNode -> next = temp -> next;
        
    } else if (head == deleteNode) {
        
        // 删除的是头节点
        head = NULL;
        deleteNode = NULL;
    } else {
        
        // 删除的是尾节点
        ListNode *node = head;
        while(node -> next != deleteNode) {
            // 找到前驱节点
            node = node -> next;
        }
        
        node -> next = NULL;
        deleteNode = NULL;
    }
    
}

链表中倒数第 k 个节点

思路：

假设链表的长度是n，倒数第 k 个节点, 如果从头计数的话, 是 n - k + 1 个节点, 第一次遍历出节点的个数n, 第二次遍历就能找到倒数的第 k 个节点
设定两个指针, 第一个指针开始遍历向前走 k - 1 步, 第二个指针步动; 从第 k 步开始, 第二个指针也开始移动, 两个节点始终保持 k - 1。当第一个指针走到尾节点时, 第二个指针刚好指向倒数第 k 个节点

  ListNode* deleteKThNode(ListNode *head, int k) {
    
    if (!head || k == 0) return 0;
    
    ListNode *slow = head;
    ListNode *fast = head;
    
    for (int i = 0; i < k - 1; i ++) {
        
        if (slow -> next == NULL) return;  // 确保 K 的值小于链表长度
        
        slow = slow -> next;
    }
    
    while (fast -> next != NULL) {
        fast = fast -> next;
        slow = slow -> next;
    }
    
    return slow;
    
}

翻转链表

  //三个指针
 struct ListNode* reverseList(struct ListNode* head) {

     if (head == NULL) return NULL;

     struct ListNode *pre = NULL;
     struct ListNode *next = NULL;
     struct ListNode *cur = head;

     while (cur != NULL) {
         next = cur -> next;
         cur -> next = pre;
         pre = cur;
         cur = next;
     }

     return pre;
 }

// 递归
struct ListNode* reverseList(struct ListNode* head) {
    
    if (head == NULL || head -> next == NULL) return head;
    
    struct ListNode *nextNode = head -> next;
    struct ListNode *reverse_node = reverseList(nextNode);
    nextNode -> next = head;
    head -> next = NULL;
    return reverse_node;
}