搞懂单链表常见面试题

亦凉 2022-01-14 01:09 206阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

# 搞懂单链表常见面试题 #

> Hello 继上次的 [搞懂基本排序算法][Link 1]，这个一星期，我总结了，我所学习和思考的单链表基础知识和常见面试题，这些题有的来自 《剑指 offer》 ,有的来自《程序员代码面试指南》，有的来自 leetCode，不是很全面，但都具有一定代表性，相信大家看完以后一定跟我一样，对面试的时候算法题又多了一份自信。不过文章仍然是又臭又长，希望大家备好咖啡，火腿肠，方便面之类的，慢慢看，如果我有哪些理解不对的地方，也希望大家能在评论区为我指出，也算是对我码这么多字的认可吧。

## 什么是单链表 ##

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里，它们可以不是连续的因为他们每个节点保存着下一个节点的引用（地址），所以较之数组来说这是一个优势。

对于单链表的一个节点我们经常使用下边这种代码表示：

public class Node{
        //节点的值
        int value；
        //指向下一个节点的指针（java 中表现为下一个节点的引用）
        Node next；
        
        public void Node(int value){
            this.value = value;
        }
    }
    复制代码

**单链表的特点**

1.  **链表增删元素的时间复杂度为O(1),查找一个元素的时间复杂度为 O(n);**
2.  **单链表不用像数组那样预先分配存储空间的大小，避免了空间浪费**
3.  **单链表不能进行回溯操作，如：只知道链表的头节点的时候无法快读快速链表的倒数第几个节点的值。**

## 单链表的基本操作 ##

上一节我们说了什么是单链表，那么我们都知道一个数组它具有增删改查的基本操作，那么我们单链表作为一种常见的数据结构类型也是具有这些操作的那么我们就来看下对于单链表有哪些基本操作：

### 获取单链表的长度 ###

由于单链表的存储地址不是连续的，链表并不具有直接获取链表长度的功能，对于一个链表的长度我们只能一次去遍历链表的节点，直到找到某个节点的下一个节点为空的时候得到链表的总长度，注意这里的出发点并不是一个空链表然后依次添加节点后，然后去读取已经记录的节点个数，而是已知一个链表的头结点然后去获取这个链表的长度：

public int getLength(Node head){
        
        if(head == null){
            return 0;
        }
        
        int len = 0;
        while(head != null){
            len++;
            head = head.next;
        }  
        return len;  
    }
    复制代码

### 查询指定索引的节点值或指定值得节点值的索引 ###

由于链表是一种非连续性的存储结构，节点的内存地址不是连续的，也就是说链表不能像数组那样可以通过索引值获取索引位置的元素。所以链表的查询的时间复杂度要是O(n)级别的，这点和数组查询指定值得元素位置是相同的，因为你要查找的东西在内存中的存储地址都是不一定的。

/** 获取指定角标的节点值 */
        public int getValueOfIndex(Node head, int index) throws Exception {
    
            if (index < 0 || index >= getLength(head)) {
                throw new Exception("角标越界！");
            }
    
            if (head == null) {
                throw new Exception("当前链表为空！");
            }
    
            Node dummyHead = head;
    
            while (dummyHead.next != null && index > 0) {
                dummyHead = dummyHead.next;
                index--;
            }
    
            return dummyHead.value;
        }
    
        
        /** 获取节点值等于 value 的第一个元素角标 */
        public int getNodeIndex(Node head, int value) {
        
                int index = -1;
                Node dummyHead = head;
        
                while (dummyHead != null) {
                    index++;
                    if (dummyHead.value == value) {
                        return index;
                    }
                    dummyHead = dummyHead.next;
                }
        
                return -1;
        }
    
    复制代码

### 链表添加一个元素 ###

学过数据结构的朋友一定知道链表的插入操作，分为头插法，尾插法，随机节点插入法，当然数据结构讲得时候也是针对一个已经构造好的（保存了链表头部节点和尾部节点引用）的情况下去插入一个元素，这看上去很简单，如果我们在只知道一个链表的头节点的情况下去插入一个元素，就不是那么简单了，就对于头插入法我们只需要构造一个新的节点，然后将这个节点的 next 指针指向已知链表的头节点就可以了。

1、 在已有链表头部插入一个节点

public Node addAtHead(Node head, int value){
         Node newHead = new Node(value);
         newHead.next = head;
         return newHead;
    }
    复制代码

**2、在已有链表的尾部插入一个节点：**

public void addAtTail(Node head, int value){
         Node node = new Node(value);
         Node dummyHead = head;
         
         //找到未节点 注意这里是当元素的下一个元素为空的时候这个节点即为未节点
         while( dummyHead.next != null){
            dummyHead = dummyHead.next;
         }
         
         dummyHead.next = node;   
    }
    复制代码

**3、在指定位置添加一个节点**

// 注意这里 index 从 0 开始
     public Node insertElement(Node head, int value, int index) throws Exception {
       //为了方便这里我们假设知道链表的长度
       int length = getLength(head);
       if (index < 0 || index >= length) {
           throw new Exception("角标越界！");
       }
    
       if (index == 0) {
           return addAtHead(head, value);
       } else if (index == length - 1) {
           addAtTail(head, value);
       } else {
    
           Node pre = head;
           Node cur = head.next;
           //
           while (pre != null && index > 1) {
               pre = pre.next;
               cur = cur.next;
               index--;
           }
    
           //循环结束后 pre 保存的是索引的上一个节点 而 cur 保存的是索引值当前的节点
           Node node = new Node(value);
           pre.next = node;
           node.next = cur;
       }
       return head;
    }
    
    复制代码

在指定位置添加一个节点，首先我们应该找到这个索引所在的节点的前一个，以及该节点，分别记录这两个节点，然后将索引所在节点的前一个节点的 next 指针指向新节点，然后将新节点的 next 指针指向插入节点即可。与其他元素并没有什么关系，所以单链表插入一个节点时间复杂度为 O(1)，而数组插入元素就不一样了如果将一个元素插入数组的指定索引位置，那么该索引位置以后元素的索引位置(内存地址)都将发生变化，所以一个数组的插入一个元素的时间复杂度为 O(n);所以链表相对于数组插入的效率要高一些，删除同理。

### 链表删除一个元素 ###

由于上边介绍了链表添加元素的方法这里对于链表删除节点的方法不在详细介绍直接给出代码：

1、 删除头部节点 也就是删除索引为 0 的节点：

public Node deleteHead(Node head) throws Exception {
            if (head == null) {
                throw new Exception("当前链表为空！");
            }
            return head.next;
        }
    复制代码

2、 删除尾节点

public void deleteTail(Node head) throws Exception {
    
            if (head == null) {
                throw new Exception("当前链表为空！");
            }
    
            Node dummyHead = head;
            while (dummyHead.next != null && dummyHead.next.next != null) {
                dummyHead = dummyHead.next;
            }
            dummyHead.next = null;
        }
    
    复制代码

3、 删除指定索引的节点：

public Node deleteElement(Node head, int index) throws Exception {
    
       int size = getLength(head);
       
       if (index < 0 || index >= size) {
           throw new Exception("角标越界！");
       }
    
       if (index == 0) {
           return deleteHead(head);
       } else if (index == size - 1) {
           deleteTail(head);
       } else {
           Node pre = head;
    
           while (pre.next != null && index > 1) {
               pre = pre.next;
               index--;
           }
    
           //循环结束后 pre 保存的是索引的上一个节点 将其指向索引的下一个元素
           if (pre.next != null) {
               pre.next = pre.next.next;
           }
       }
    
       return head;
    }
    复制代码

**由单链表的增加删除可以看出，链表的想要对指定索引进行操作（增加，删除），的时候必须获取该索引的前一个元素。记住这句话，对链表算法题很有用。**

## 单链表常见面试题 ##

介绍了链表的常见操作以后，我们的目标是学习链表常见的面试题目，不然我们学他干嘛呢，哈哈~ 开个玩笑那么我们就先从简单的面试题开始：

### 寻找单链表的中间元素 ###

同学们可能看到这道面试题笑了，咋这么简单，拿起笔来就开始写，遍历整个链表，拿到链表的长度len，再次遍历链表那么位于 len/2 位置的元素就是链表的中间元素。

咱也不能说这种方法不对，想想一下一个腾讯的面试官坐在对面问这个问题，这个回答显然连自己这一关都很难过去。那么更渐快的方法是什么呢？或者说时间复杂度更小的方法如何实现这次查找？这里引出一个很关键的概念就是 **快慢指针法**，这也是面试官想考察的。

假如我们设置 两个指针 `slow、fast` 起始都指向单链表的头节点。其中 `fast` 的移动速度是 `slow` 的2倍。当 `fast` 指向末尾节点的时候，`slow` 正好就在中间了。想想一下是不是这样假设一个链表长度为 6 ， `slow` 每次一个节点位置， `fast` 每次移动两个节点位置，那么当`fast = 5`的时候 `slow = 2` 正好移动到 2 的节点的位置。

所以求解链表中间元素的解题思路是：

public Node getMid(Node head){
          if(head == null){
             return null;
          }
          
          Node slow = head;
          Node fast = head;
          
          // fast.next = null 表示 fast 是链表的尾节点
          while(fast != null && fast.next != null){
             fast = fast.next.next;
             slow = slow.next;
          }
          return slow;
        }
    
    复制代码

### 判断一个链表是否是循环链表 ###

首先此题也是也是考察快慢指针的一个题，也是快慢指针的第二个应用。先简单说一下什么循环链表，循环链表其实就是单链表的尾部指针指向头指针，构建成一个环形的链表，叫做循环链表。 如 `1 -> 2 - > 3 -> 1 -> 2 .....`。为什么快慢指针再循环链表中总能相遇呢？你可以想象两个人在赛跑，A的速度快，B的速度慢，经过一定时间后，A总是会和B相遇，且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍。这也就是 **Floyd判环(圈)算法**。

那么如何使用快慢指针去判断一个链表是否为环形链表呢：

private static boolean isLoopList(Node head){
    
            if (head == null){
                return false;
            }
    
            
            Node slow = head;
            Node fast = head.next;
            
            //如果不是循环链表那么一定有尾部节点 此节点 node.next = null
            while(slow != null && fast != null && fast.next != null){
                if (fast == slow || fast.next == slow){
                    return true;
                }
                // fast 每次走两步  slow 每次走一步
                fast =fast.next.next;
                slow = slow.next;
            }
            //如果不是循环链表返回 false
            return false;
        }
    
    复制代码

### 已知一个单链表求倒数第 N 个节点 ###

为什么这个题要放在快慢指针的后边呢，因为这个题的解题思想和快慢指针相似，我们可以想一下：如果我们让快指针先走 n-1 步后，然后让慢指针出发。快慢指针每次都只移动一个位置，当快指针移动到链表末尾的时候，慢指针是否就正处于倒数第 N 个节点的位置呢。

是这里把这两个指针称之为快慢指针是不正确的，因为快慢指针是指一个指针移动的快一个指针移动的慢，而此题中 快指针只是比慢指针先移动了 n-1 个位置而已，移动速度是相同的。

如果上边的讲解不好理解，这里提供另外一种思路，就是想象一下，上述快慢指针的移动过程，是否就相当于一个固定窗口大小为 n 的滑动窗口：

1.  n = 1 fast 指针不移动 fast 到达最后一个节点 即 fast.next 的时候 slow 也到达尾部节点满条件
2.  n = len fast 指针移动 n-1（len -1 ） 次 fast 到达最后一个节点 slow 位于头节点不变 满足条件 两个临界值均满足我们这种假设。
3.  1< n < len 的时候我们假设 n = 2 ，那么 fast 比 slow 先移动一步,也就是窗口大小为 2， 那么当 fast.next = null 即 fast 已经指向链表最后一个节点的时候，slow 就指向了 倒数第二个节点。

下面我们来看下函数实现：

/**
         * 注意我们一般说倒数第 n 个元素 n 是从 1 开始的
         */
        private Node getLastIndexNode(Node head, int n) {
    
            // 输入的链表不能为空，并且 n 大于0
            if (n < 1 || head == null) {
                return null;
            }
    
            n = 10;
            // 指向头结点
            Node fast = head;
            // 倒数第k个结点与倒数第一个结点相隔 n-1 个位置
            // fast 先走 n-1 个位置
            for (int i = 1; i < n; i++) {
                // 说明还有结点
                if (fast.next != null) {
                    fast = fast.next;
                }else {
                    // 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
                    return null;
                }
            }
    
            Node slow = head;
            // fast 还没有走到链表的末尾，那么 fast 和 slow 一起走，
            // 当 fast 走到最后一个结点即，fast.next=null 时，slow 就是倒数第 n 个结点
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            // 返回结果
            return slow;
    }
    复制代码

### 删除单链表的倒数第 n 个节点 ###

看到这个题时候乐了，这考察的知识点不就是一道求解倒数第 n 个节点的进化版么。但是我们也说过，如果想操作链表的某个节点(添加，删除)还必须知道这个节点的前一个节点。所以我们删除倒数第 n 个元素就要找到倒数第 n + 1 个元素。然后将倒数第 n + 1个元素 p 的 next 指针 `p.next` 指向 `p.next.next` 。

我们找到倒数第 n 个节点的时候，先让 fast 先走了 n-1 步，那么我们删除倒数第 n 个节点的时候就需要 让 fast 先走 n 步，构建一个 n+1 大小的窗口，然后 fast 和 slow 整体平移到链表尾部，slow 指向的节点就是 倒数第 n+1 个节点。

这里我们还可以使用滑动窗口的思想来考虑临界值：

1.  n = 1 的时候我们需要构建的窗口为 2,也就是当 fast.next = null 的时候 slow 在的倒数第二个节点上，那么可想而知是满足我们的条件的。
2.  当 1 < n < len 的时候我们总是能构建出这样的一个 len + 1大小的窗口，n 最大为 len -1 的时候，slow 位于头节点，fast 位于未节点，删除倒数第 n 个元素，即删除正数第二个节点，slow.next = slow.next.next 即可。
3.  当 n > len 的时候可想而知，我们要找的倒数第 n 个元素不存在，此时返回 头节点就好了
4.  n = len 的时候比较特殊，循环并没有因为倒数第 len 个元素不存在而终止，并进行了 `fast = fast.next;` 循环结束后 fast 指向 null , 且此时 slow 位于头节点，所以我们要删除的节点是头节点，只需要在循环结束后判断 如果 `fast == null` 返回 `head.next` 即可

下面我们来看解法：

/**
     * 删除倒是第 n 个节点 我们就要找到倒数第 n + 1 个节点， 如果 n > len 则返回原列表
     */
    private Node deleteLastNNode(Node head, int n) {
    
       if (head == null || n < 1) {
           return head;
       }
    
       Node fast = head;
       
       //注意 我们要构建长度为 n + 1 的窗口 所以 i 从 0 开始
       for (int i = 0; i < n; i++) {
           //fast 指针指向倒数第一个节点的时候，就是要删除头节点
           if (fast == null) {
               return head;
           } else {
               fast = fast.next;
           }
       }
    
       // 由于 n = len 再循环内部没有判断直接前进了一个节点，临界值 n = len 的时候 循环完成或 fast = null
       if (fast == null){
           return head.next;
       }
    
       //此时 n 一定是小于 len 的 且 fast 先走了 n 步
       Node pre = head;
    
       while (fast.next != null) {
           fast = fast.next;
           pre = pre.next;
       }
    
       pre.next = pre.next.next;
    
       return head;
    }
    复制代码

### 旋转单链表 ###

> 题目：给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数。 如给出链表为 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

做完，删除倒数第 n 个节点的题，我们在看着道题是不是很简单了，这道题的本质就是，找到 k 位置节点 将其变成尾节点，然后原来链表的尾节点指向原来的头节点

private Node rotateList(Node head, int n) {
    
       int start = 1;
    
       Node fast = head;
    
       //先让快指针走 n 给个位置
       while (start < n && fast.next != null) {
           fast = fast.next;
           start++;
       }
    
    
       //循环结束后如果 start < n 表示 n 整个链表还要长 旋转后还是原链表
       //如果 fast.next = null 表示 n 正好等于原链表的长度此时也不需要旋转
       if (fast.next == null || start < n) {
           return head;
       }
    
       //倒数第 n + 1个节点
       Node pre = fast;
       //旋转后的头节点
       Node newHead = fast.next;
    
       while (fast.next != null) {
           fast = fast.next;
       }
       //原链表的最后一个节点指向原来的头节点
       fast.next = head;
       //将旋转的节点的上一个节点变为尾节点
       pre.next = null;
    
       return newHead;
    }
    
    复制代码

### 翻转单链表 ###

翻转一个单链表，要求额外的空间复杂度为 O(1)

翻转单链表是我感觉比较难的基础题，那么先来屡一下思路：一个节点包含指向下一节点的引用，翻转的意思就是对要原来指向下一个节点引用指向上一个节点

1.  找到当前要反转的节点的下一个节点并用变量保存因为下一次要反转的是它
2.  然后让当前节点的 next 指向上一个节点， 上一个节点初始 null 因为头结点的翻转后变为尾节点
3.  当前要反转的节点变成了下一个要比较元素的上一个节点，用变量保存
4.  当前要比较的节点赋值为之前保存的未翻转前的下一个节点
5.  当前反转的节点为 null 的时候，保存的上一个节点即翻转后的链表头结点

ok，不知道按照上边我写的步骤能否理解一个链表的翻转过程。如果不理解自己动手画一下可能更好理解哈，注意在画的时候一次只考虑一个节点，且不要考虑已经翻转完的链表部分。

下面我们来看下实现过程：

public Node  reverseList(Node head){
       //头节点的上一个节点为 null
       Node pre = null;
       Node next = null;
       
       while(head != null){
           next = head.next;
           head.next = pre;
           pre = head;
           head = next;
       }
    }
    复制代码

### 翻转部分单链表 ###

> 题目要求：要求 0 < from < to < len 如果不满足则不翻转

这类题还有一类进阶题型，就是翻转链表 from 位置到 to 位置的节点，其实翻转过程是相似的，只是我们需要找到位于 from 的前一个节点，和 to 的下一个节点 翻转完 from 和 to 部分后将 from 的上一个节点的 next 指针指向翻转后的to，将翻转后 from 节点的 next 指针指向 to 节点下一个节点。

1.  遍历整个链表 遍历过程需要统计链表的长度 len ，from 节点的前一个节点 fPosPre , 翻转开始的节点 from ，翻转结束的节点 to ，节点to 节点的后一个节点 tPosNext 。
2.  循环后判断条件 0 < from < to < len 的条件是否满足，如果不满足返回 head
3.  进行 from 到 to 节点翻转
4.  翻转完后判断 如果翻转的起点不是 head 则返回 head,如果反转的链表是起点，那么翻转后 toPos 就是头结点。

下面我们开看代码(你可能有更简便的解法，省去几个变量，但是下面的解法应该是最好理解的);

private Node reversePartList(Node head, int from, int to) {
            
            Node dummyHead = head;
    
            int len = 0;
    
            Node fPosPre = null;
            Node tPosNext = null;
            Node toPos = null;
            Node fromPos = null;
    
            while (dummyHead != null) {
                //因为 len = 0 开始的所以 len 先做自增一
                len++;
    
                if (len == from) {
                    fromPos = dummyHead;
                } else if (len == from - 1) {
                    fPosPre = dummyHead;
                } else if (len == to + 1) {
                    tPosNext = dummyHead;
                } else if (len == to) {
                    toPos = dummyHead;
                }
    
                dummyHead = dummyHead.next;
            }
    
            //不满足条件不翻转链表
            if (from > to || from < 0 || to > len || from > len) {
                return head;
            }
    
    
            Node cur = fromPos;
            Node pre = tPosNext;
            Node next = null;
    
            while (cur != null && cur != tPosNext) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            // 如果翻转的起点不是 head 则返回 head
            if (fPosPre != null) {
                fPosPre.next = pre;
                return head;
            }
            // 如果反转的链表是起点，那么翻转后 toPos 就是头结点
            return toPos;
        }
    复制代码

### 单链表排序 ###

在我的上一篇文章中说到了数组基本的排序方法 [搞懂基本排序方法][Link 2]，对于链表来说也有上述几种排序方法，如果感兴趣的朋友也可以使用冒泡排序，选择排序，快速排序去实现单链表的排序，由于链表的不可回溯行，对于链表来说归并排序是个不错的排序方法。我们知道归并通过递归，可以实现，那么对于单链表来说也是可以的。

#### 单链表的归并排序 ####

归并的中心思想在于在于已知两个链表的时候，如果按顺序归并这两个链表。其实这也是一道面试题按照元素的大小合并两个链表那么我们就先看下如何合并两个链表 我们称这个过程为 merge 。

private Node merge(Node l, Node r) {
    
       //创建临时空间
       Node aux = new Node();
       Node cur = aux;
    
       //由于链表不能方便的拿到链表长度 所以一般使用 while l == null 表示链表遍历到尾部
       while (l != null && r != null) {
           if (l.value < r.value) {
               cur.next = l;
               cur = cur.next;
               l = l.next;
           } else {
               cur.next = r;
               cur = cur.next;
               r = r.next;
           }
       }
       //当有一半链表遍历完成后 另外一个链表一定只剩下最后一个元素（链表为基数）
       if (l != null) {
           cur.next = l;
       } else if (r != null) {
           cur.next = r;
       }
    
       return aux.next;
    }
    复制代码

返回的 Node 节点为归并完成后的链表头节点。那么归并排序的核心过程也完成了，想想我们想要归并一个数组还需要一个划分操作 **中心节点 mid 是谁**，看到这里是不是笑了，之前我们已经讲过如何寻找一个链表的中间元素，那么是不是万事具备了，ok 我们来实现链表的归并排序：

private Node mergeSort(Node head) {
    
       //递归退出的条件 当归并的元素为1个的时候 即 head.next 退出递归
       if (head == null || head.next == null) {
           return head;
       }
    
       Node slow = head;
       Node fast = head;
    
       //寻找 mid 值
       while (fast.next != null && fast.next.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
    
       Node left = head;
       Node right = slow.next;
    
       //拆分两个链表 如果设置链表的最后一个元素指向 null 那么 left 永远等于 head 这链表 也就无法排序
       slow.next = null;
       
       //递归的划分链表
       left = mergeSort(left);
       right = mergeSort(right);
    
       return merge(left, right);
    }
    复制代码

#### 单链表的插入排序 ####

回想一下数组的插入排序，我们从第二个数开始遍历数组，如果当前考察的元素值比下一个元素的值要大，则下一个元素应该排列排列在当前考察的元素之前，所以我们从已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于新元素，将该元素移到下一位置（赋值也好，交换位置也好）。但是由于链表的不可回溯性，我们只能从链表的头节点开始找，这个元素应该要在的位置。

我们来看下代码实现：

public Node insertionSortList(Node head) {
            if (head == null || head.next == null) return head;
    
            Node dummyHead = new Node(0)；
            Node p = head;
            dummyHead.next = head;
          //p 的值不小于下一节点元素考察下一节点
            while (p.next != null) {
                if (p.value <= p.next.value) { 
                    p = p.next;
                } else {
                    //p 指向 4
                    Node temp = p.next;
                    Node q = dummyHead;
                    p.next = p.next.next;
    
                    //从头遍历链表找到比当前 temp 值小的第一个元素插入其后边 整个位置一定在 头节点与 q 节点之间
                    while (q.next.value < temp.value && q.next != q)
                        q = q.next;
    
                    temp.next = q.next;
                    //重新连接链表 注意 else 的过程并没有改变 p 指针的位置
                    q.next = temp;
                }
            }
            return dummyHead.next;
        }
    复制代码

### 划分链表 ###

> 题目 ： 按某个给定值将链表划分为左边小于这个值，右边大于这个值的新链表 如一个链表 为 `1 -> 4 -> 5 -> 2` 给定一个数 3 则划分后的链表为 `1-> 2 -> 4 -> 5`

此题不是很难，就是遍历一遍链表，就可以完成，我们新建一两个链表，如果遍历过程中，节点值比给定值小则划在左链表中，反之放在右链表中，遍历完成后拼接两个链表就好。不做过多解释直接看代码。

private Node partition(Node head , int x){
        if(head == null){
            return = null;
        }
        
        Node left = new Node(0);
        Node right = new Node(0);
        
        Node dummyLeft = left;
        Node dummyRight = right;
        
        while(head != null){
            if(head.value < x){
                dummyLeft.next = head;
                dummyLeft = dummyLeft.next;
            }else{
                dummyRight.next = head;
                dummyRight = dummyRight.next;
            }
            head = head.next;
        }
        
        dummyLeft.next = right.next;
        right.next = null;
        
        return left.next;
     }
    复制代码

### 链表相加求和 ###

> 题目： 假设链表中每一个节点的值都在 0-9 之间，那么链表整体可以代表一个整数。 例如： 9->3->7 可以代表 937 给定两个这样的链表，头节点为 head1 head2 生成链表相加的新链表。 如 9->3->7 和 6 -> 3 生成的新链表应为 1 -> 0 -> 0 -> 0

此题如果明白题意的情况并不难解决，首先理解怎么取加两个链表，即链表按照，尾节点往前的顺序每一位相加，如果有进位则在下一个节点相加的时候算上，每一位加和为新链表的一个结点。这看上去跟数学加法一样。所以我们的解题思路为：

1.  翻转要相加的两个链表，这样就可以从原链表的尾节点开始相加。
2.  同步遍历两个逆序链表，每一个节点的值相加，通过是要使用变量记录是否进位。
3.  当链表遍历完成后 判断是否还有进位 如果有再添加一个结点，
4.  再次翻转两个链表使其复原，并翻转新链表，则得到的题解。

private Node addLists(Node head1, Node head2) {
            head1 = reverseList(head1);
            head2 = reverseList(head2);
            //进位标识
            int ca = 0;
            int n1 = 0;
            int n2 = 0;
            int sum = 0;
    
            Node addHead = new Node(0);
            Node dummyHead = addHead;
    
            Node cur1 = head1;
            Node cur2 = head2;
    
            while (cur1 != null || cur2 != null) {
                n1 = cur1 == null ? 0 : cur1.value;
                n2 = cur2 == null ? 0 : cur2.value;
    
                sum = n1 + n2 + ca;
    
                Node node = new Node(sum % 10);
                System.out.println( sum % 10);
                ca = sum / 10;
    
                dummyHead.next = node;
    
                dummyHead = dummyHead.next;
    
                cur1 = cur1 == null ? null : cur1.next;
                cur2 = cur2 == null ? null : cur2.next;
            }
    
            if (ca > 0) {
                dummyHead.next = new Node(ca);
            }
    
            head1 = reverseList(head1);
            head2 = reverseList(head2);
    
            addHead = addHead.next;
            return reverseList(addHead);
        }
        
        private  Node reverseList(Node head) {
            Node cur = head;
            Node pre = null;
            Node next = null;
    
            while (cur != null) {
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            //注意这里返回的是赋值当前比较元素
            return pre;
        }
    
    复制代码

### 删除有序/无序链表中重复的元素 ###

#### 删除有序链表中的重复元素 ####

删除有序链表中的重复元素比较简单，因为链表本身有序，所以如果元素值重复，那么必定相邻，所以删除重复元素的方法为:

如一个链表为 36 -> 37 -> 65 -> 76 -> 97 -> 98 -> 98 -> 98 -> 98 -> 98 删除重复元素后为: 36 -> 37 -> 65 -> 76 -> 97 -> 98

private void delSortSame(Node head) {
            if (head == null || head.next == null) {
                return;
            }
    
            Node dummy = head;
            while (dummy.next != null) {
                if (dummy.value == dummy.next.value) {
                    dummy.next = dummy.next.next;
                } else {
                    dummy = dummy.next;
                }
            }
        }
    复制代码

#### 删除无序链表中的重复元素 ####

删除无序链表中的重复元素，就要求我们必须使用一个指针记住当前考察元素 cur 的上一个元素 pre ，并以此遍历考察元素之后的所有节点，如果有重复则将 pre 指针的 next 指针指向当 cur.next; 重复遍历每个节点，直至链表结尾。

如一个链表删除重复元素前为: 0 -> 0 -> 3 -> 5 -> 3 -> 0 -> 1 -> 4 -> 5 -> 7 删除重复元素后为: 0 -> 3 -> 5 -> 1 -> 4 -> 7

private void delSame(Node head) {
    
       if (head == null || head.next == null) {
           return;
       }
       
       Node pre = null;
       Node next = null;
       Node cur = head;
    
       while (cur != null) {
           //当前考察的元素的前一个节点
           pre = cur;
           //当前考察元素
           next = cur.next;
           //从遍历剩余链表删除重复元素
           while (next != null) {
               if (cur.value == next.value) {
                   //删除相同元素
                   pre.next = next.next;
               }else {
                   //移动指针
                   pre = next;
               }
               //移动指针
               next = next.next;
           }
           //考察下一个元素
           cur = cur.next;
       }
    }
    
    复制代码

### 重排链表 ###

其实这也是一系列的题目，主要考察了我们对于额外空间复杂度为`O(1)` 的链表操作。我们先看第一道题：

#### 按照左右半区的方式重新排列组合单链表 ####

> 题目 给定一个单链表L： `L0→L1→…→Ln-1→Ln`, 重新排列后为 `L0→Ln→L1→Ln-1→L2→Ln-2→…` 要求必须在不改变节点值的情况下进行原地操作。

我们先来分析一下题目，要想重排链表，必须先找到链表的中间节点，然后分离左右两部链表，然后按左边一个，右边一个的顺序排列链表。我们假设链表为基数的时候， N/2 位置的节点算左半链表， 那么右半链表就会比左半链表多一个节点。当左半链表为最后一个节点的时候我们只需要将剩余的右半链表设为其下一个节点即可。 N 为偶数的时候就好说了，N/2 + 1 为右半链表的开始，重拍最后只需要将左半链表为最后一个节点指向 null，恰巧此时右半链表为 null 所以重拍最后一步就是 `left.next = right` 下面我们来看题解：

private void relocate1(Node head) {
       //如果链表长度小于2 则不需要重新操作
       if (head == null || head.next == null) {
           return;
       }
    
       //使用快慢指针 遍历链表找到链表的中点
       Node mid = head;
       Node right = head.next;
    
       while (right.next != null && right.next.next != null) {
           mid = mid.next;
           right = right.next.next;
       }
    
       //拆分左右半区链表
       right = mid.next;
       mid.next = null;
    
       //按要求合并
       mergeLR(head, right);
    
    }
    
    private void mergeLR(Node left, Node right) {
       Node temp = null;
       while (left.next != null) {
           temp = right.next;
    
           right.next = left.next;
           left.next = right;
    
           //这里每次向后移动两个位置 也就是原来的 left.next
           left = right.next;
           right = temp;
       }
       left.next = right;
    }
    复制代码

#### 今日头条的一个重排链表题目 ####

> 给定一个链表 `1 -> 92 -> 8 -> 86 -> 9 -> 43 -> 20` 链表的特征是奇数位升序，偶数位为降序，要求重新排列链表并保持链表整体为升序

这道题和左右半区重排链表类似，其实这可以理解为一个已经进行重排后的链表，现在要执行上一道重排的逆过程。要满足这个条件，我们必须假设偶数位最小的节点大于奇数位最大的元素。我想出题人也是这意思。如果不是的话也不麻烦上边我们也讲了归并排序的方法，只是一次归并而已。下面来看满足数位最小的节点大于奇数位最大的元素的解法：

> 此题考察了面试者对链表的基本操作以及如何翻转一个链表

private Node relocate2(Node head) {
    
            //新建一个左右连个链表的头指针
            Node left = new Node();
            Node right = new Node();
    
    
            Node dummyLeft = left;
            Node dummyRight = right;
    
            int i = 0;
            while (head != null) {
                //因为 i 从0 开始 链表的头节点算是奇数位所以 i 先自增 再比较
                i++;
                if (i % 2 == 0) {
                    dummyRight.next = head;
                    dummyRight = dummyRight.next;
                } else {
                    dummyLeft.next = head;
                    dummyLeft = dummyLeft.next;
                }
                //每次赋值后记得将下一个节点置位 null
                Node next = head.next;
                head.next = null;
                head = next;
            }
    
            right = reverseList(right.next);
            dummyLeft.next = right;
    
            return left.next;
        }
    复制代码

### 判断两个单链表（无环）是相交 ###

> 题目： 判断两个无环链表是否相交，如果相交则返回第一个相交节点，如果不想交返回 null 。

我们来分析一下这道题，我们假设两个单链表相交，那从相交的节点开始到结束，一直到两个链表都结束，那么后边这段链表相当于是共享的。我们还可以知道如果将这两个链表的末尾对齐，这两个链表的尾节点一定是相等的，所以我们的解题思路如下：

1.  想让一个链表遍历一遍，并记录其长度
2.  在遍历另一个链表，遍历过程中 n 每次自减一
3.  遍历结束后，指针 cur1 指向链表 head1 的最后一个节点，同理指针 cur2 指向 head2 的最后一个节点，如果此时 cur1 != cur2 那么根据题意这两个链表不想交。
4.  遍历结束后，我们假设 hea1 要比 head2 长，那么 n 一定为正数，代表了 head1 头节点指针如果向右移动 n 个数 剩余链表的长度将和 head2 一样长
5.  此后 point1 和 point2 一起走那么这两个 point 指向的节点总会相等，第一次相等的点即为两个链表相交的点。

private Node intersect(Node head1, Node head2) {
            if (head1 == null || head2 == null) {
                return null;
            }
    
            Node cur1 = head1;
            Node cur2 = head2;
    
            int n = 0;
    
            while (cur1.next != null) {
                n++;
                cur1 = cur1.next;
            }
    
            while (cur2.next != null) {
                n--;
                cur2 = cur2.next;
            }
    
            if (cur1 != cur2) {
                return null;
            }
    
            //令 cur1 指向 较长的链表，cur2 指向较短的链表
            if (n > 0) {
                cur1 = head1;
                cur2 = head2;
            } else {
                cur1 = head2;
                cur2 = head1;
            }
    
            n = Math.abs(n);
    
            //较长的链表先走 n 步
            while (n != 0) {
                cur1 = cur1.next;
            }
    
            //两个链表一起走 第一次相等节点即为相交的第一个节点
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            
            return cur1;
        }
    复制代码

## 总结 ##

上篇文章搞懂排序算法评论有人说，文章太长了。没想到这篇文章写着写着又这么长了。还请大家耐下心来看，每到题自己耐下心来做一遍。等大家都搞懂以后，相信大家也就差不多无所畏惧单链表的面试题了。

欢迎大家关注我的个人博客地址，本文算法题也上传到我的 github上了。[NodePractice][] 后续我将开始学习数组，和字符串的算法题。相信不久将来又能见到我的又臭又长的文章了。

最后 **愿天不负有心人。**

转载于:https://my.oschina.net/u/2935389/blog/3030367

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/47150e56a6ae4b8a96b3432e5d9dda54.png
[Link 1]: https://juejin.im/user/56793b0860b2b7af14c637db/posts
[Link 2]: https://juejin.im/post/5a96d6b15188255efc5f8bbd
[NodePractice]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2FImportEffort%2FWLeetCode%2Fblob%2Fac98e98934e79fe93b2a5a99bbe52bf32398a6c6%2Fsrc%2FNodePractice%2FNodePractice.java