【面试算法】——链表（一）

一、链表

1.链表问题算法难度不高，但是考察代码实现能力

2.链表和数组都是一种线性结构

• 数组是一段连续的存储空间
• 链表空间不一定是保证连续的，为临时分配的

3.链表的分类

4.链表问题代码实现的关键点

（1）链表调整函数的返回类型，根据要求往往是节点的类型

（2）处理链表过程中，先采用画图的方式理清逻辑

（3）链表问题对于边界条件讨论要求严格

5.链表插入和删除的注意事项

（1）特殊处理链表为空，或者链表长度为1的情况

（2）注意插入操作的调整过程

（3）注意删除操作的调整过程

注意点：头尾节点及空节点需要特殊考虑

6.链表的翻转操作

（1）特殊处理链表为空，或者链表长度为1的情况

大量的链表问题可以使用额外的数据结构来简化调整过程，但链表问题最优解往往是不使用额外的数据结构的方法。

 

2、环形链表插值

题型：

给定一个整数num，如何在节点值有序的环形链表中插入一个节点为num的节点，并且保证这个环形单链表依然有序。

思路：

对于链表的算法题目，我们需要考虑到原链表为空的情况和最后返回链表头部节点是否需要改变的情况。我们将num转换为一个节点类型数据。

首先，如果原链表为空，那么我们将num节点的next指针指向自己，让num自己成为一个环形链表，最后返回num节点；

如果原链表不为空，那么我们设置两个变量previous和current变量，将两个变量分别等于原链表的头结点和第二个节点，然后让previous和current变量同步移动下去，如果出现previous的值小于等于num，current的值大于等于num，那么就说明num应该插入到当前previous和current之间。

如果出现num比原链表中的所有数都大或者所有数都小的情况，num都会被插入到原链表的头节点前面，但是返回的头结点不同。

代码举例：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class InsertValue {
    public ListNode insert(int[] A, int[] nxt, int val) {
        // write code here
        //如果原链表为空
        if(A.length == 0){
            ListNode num = new ListNode(val);
            num.next = num;
            return num;
        }
        //构造环形链表
        ListNode head = new ListNode(A[0]);
        ListNode cur = head;
        for(int i=0;i<A.length-1;i++){
            ListNode next = new ListNode(A[nxt[i]]);
            cur.next = next;
            cur = next;
        }
        
        //插入
        ListNode preNode = head;
        ListNode nextNode = preNode.next;
        //如果num小于head的值
        if(val<head.val){
            ListNode numNode = new ListNode(val);
            numNode.next = head;
            return numNode;
        }
        while(nextNode!=null && val>nextNode.val){
            preNode = nextNode;
            nextNode = preNode.next;
        }
        ListNode numNode = new ListNode(val);
        numNode.next = nextNode;
        preNode.next = numNode;
        return head;
    }
}

3、访问单个节点的删除练习题

题型：

给定一个链表中的节点node，但不给定整个链表的头节点，如何在链表中删除node？请实现这个函数，要求时间复杂度为O（1）。

思路：

如果是双向链表，那么比较简单，因为我们可以通过previous找到被删除节点的前节点，但是如果是单向链表，那么我们无法访问到被删除节点的前节点，有一种不太完美的做法，就是进行值的拷贝，我们将删除节点的下一个节点的值赋值给删除节点，然后将删除节点的指针指向下下一个节点，但是这种方式对于删除尾结点存在缺陷，所以我们只能通过把尾结点赋值为null来实现，但这并不是真正的实现。

代码举例：

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Remove {
    public ListNode removeNode(ListNode pNode, int delVal) {
        // write code here
      if (pNode == null) {
        return null;
      }
      if (pNode.val == delVal) {
          return pNode.next;
      }
      ListNode node = pNode;
      ListNode temp = pNode;
      while (node != null) {
          //这里就是复制后一个节点，然后删除后一个节点的做法
          if (node.val == delVal && node.next != null) {
              node.val = node.next.val;
              node.next = node.next.next;
              break;
          }
          //然而到尾节点还是不灵光的啦，一定需要前节点
          else if (node.val == delVal && node.next == null) {
              temp.next = null;
              break;
          }
          temp = node;
          node = node.next;
 
      }
      return pNode;
        
    }
}