[数据结构与算法]《算法系列》之链表

简介

?? 我们平时会发现如果一道题如果涉及数据结构，那么他的算法思路一般相对其它同等难度的题要简单，其实链表也一样，纯链表的题也不会特别难。了解了一些套路之后，做题方法也是有迹可寻，我们可以适当记一些模板，这样可以加快我们解题的速度，比如如何寻找中点，用虚拟节点或递归法反转链表等，其中递归是链表篇的重点，其实也整个刷题生涯中的重点，链表中的递归，回溯中的递归，二叉树和图中的递归等等，所以这里也会讲一下递归的书写模板，要重点学习。

理论基础

??链表是一种线性存储结构，采用的是链式存储。可以采用连续的存储空间，也可以采用零散的非连续存储空间。 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表示意图如下：

?? 除了以上这种单链表以外，还有双向链表和循环链表。在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点指向前一个结点，构成一个链表，就产生了双向链表的概念了。即每个节点都有两个指针。双向链表示意图如下：

循环链表其实也好理解，就是首尾节点连接在一起了罢了，我们平时写链表代码时，如非必要，要注意循环链表的产生，否则可能会导致CPU空转，出现致命BUG，循环链表示意图如下：

链表的特点

• 是一种线性存储结构。
• 节点值包含两部分，分别为数据域和指针域。
• 可以采用零散的存储空间。
• 和数组相比，内存消耗更大，主要需要多存一个指针域。
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。
• 和数组比，无固定长度，理论上来讲，只要内存没爆，能一直存。
• 线性链表还可分为单链表，双向链表，循环链表等。
• 链表节点的增加一般有头插入法和尾插入法两种。

链表类的定义：

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

解题方式

?? 解链表的题，一定要会两招，一招是递归，一招是迭代法。其中递归的写法可以分成三步走：

• 一、明确函数功能： 要清楚你写这个函数是想要做什么。

• 二、寻找递归出口： 递归一定要有结束条件，不然会永远递归下去，禁止套娃。

• 三、找出递推关系： 开始实现递归，一步一步递推出最终结果。
  递归方式主要在链表反转时，或者需要从后往前操作链表时，经常用到，写递归函数时，一定要明确递推关系和递归出口，否则不可能写好递归的。至于迭代法，其实不过就是写循环，一般比递归要好理解一些，代码也更好写，但有的题不能直接看出来用迭代法，但请相信：所有的递归都可以用循环来写。接下来看一下递归和迭代的模板：

  // 递归模板
  class Solution {
      public BBB AAA(ListNode head) {
          return helper(入参);
      }
  
      private BBB helper(入参) {
          if (终止条件) {
              return xxx;
          }
          // 函数功能
          return helper(参数); # 递归调用
      }
  }
  
  // 迭代模板
  ... 其实就是 for 或 while 循环 ...
  	for(...){
  		... ...
  	}
  
  	while(...){
  		... ...
  	}
  

  下面以反转链表这题经典题，来展示这两种方法。

  // 递归法反转链表
  class Solution {
      public ListNode reverseList(ListNode head) {
          return reverse(null, head);
      }
  
      private ListNode reverse(ListNode prev, ListNode cur) {
          if (cur == null) {
              return prev;
          }
          ListNode temp = null;
          temp = cur.next;// 先保存下一个节点
          cur.next = prev;// 反转
          // 更新prev、cur位置
          // prev = cur;
          // cur = temp;
          return reverse(cur, temp);
      }
  }
  
  // 迭代法反转链表
  class Solution {
      public ListNode reverseList(ListNode head) {
          // 申请新虚拟节点
          ListNode dummy = new ListNode(0);
          ListNode p = dummy, cur = head;
          while(cur != null){
              // 从head摘下一个头
              ListNode t = cur;
              cur = cur.next;     // cur移到下一个
              t.next = p.next;    // 头插法插入，依次反转
              p.next = t;
          }
          return dummy.next;
      }
  }
  

?? 以上迭代法的书写方式，也可以叫做虚拟头节点法，相当于递归来说，更易于我们理解。链表的题，有时申请一个虚拟头节点，题解就会豁然开朗。

解题心得

• 只要弄清链表的特性，单纯的链表题一般也不难。
• 一定要学会几种反转链表的方式，很重要。
• 递归一定要好好学习，无论是链表题，还是之后的题，都会经常用到，最好能理解并默写模板。
• 寻找链表中点，只需要用双指针，Slow前行一步，Fast前行两步，Fast到底，Slow就是中间节点了。
• 在leetcode中通常链表已经定义好了，但我们平时也要注意链表类的定义怎么写，因为面试时，是不会有人给你定义的，这些都需要你自己写。

算法题目

2. 两数相加

题目解析：将两链表直接相加，要注意进位（carry）的处理，这里可以用虚拟头节点来处理链表，会更方便。
代码如下：

/**
 * Definition for singly-linked list.
 * public caass ListNode {
 *     int bal;
 *     ListNodeint val; next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 
/**
 * 链表
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 声明一个虚拟头节点
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        // 只要有一个链表不为空，则需继续相加
        while(l1 != null || l2 != null){
            int a = (l1 != null) ? l1.val : 0;
            int b = (l2 != null) ? l2.val : 0;
            int sum = carry + a + b;
            // 无进位，则carry为零
            carry = sum / 10;
            // 节点值为个位数数值
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if(l1 != null ) l1 = l1.next;
            if(l2 != null ) l2 = l2.next;
        }
        // 若最后有进位，则新加一个节点
        if(carry > 0){
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

24. 两两交换链表中的节点

题目解析：递归整个链表，然后按两两相交的规则，重新生成新链表。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 
 /* 
  * 递归
  */
class Solution {
    public ListNode swapPairs(ListNode head) {
        return swap(head);
    }

    public ListNode swap(ListNode head){
        
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode tampA = head;
        ListNode tampB = head.next.next;
        // 按新链表的生成顺序，完成代码书写，更便于理解
        head = head.next;
        head.next = tampA;
        head.next.next = swap(tampB);
        return head;
    }
}

25. K 个一组翻转链表

题目解析：这里需要双重递归，每过K个节点，再执行递归进行链表反转这K个节点。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 双层递归
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 新的head
        ListNode newHead = head;
        // 运行至该节点
        ListNode tempA = head;
        for (int i = 0; i < k; i++) {
            if (tempA == null) {
                return head;
            }
            if (i == k - 1) {
                newHead = tempA;
            }
            tempA = tempA.next;
        }
        // 反转后的最后一个节点
        ListNode tempB = reverse(head, k);
        // 当前段最后一个节点与下一段开头相连
        tempB.next = reverseKGroup(tempA, k);
        return newHead;
    }

    /**
     * 用递归反转链表
     */
    public ListNode reverse(ListNode head, int k) {
        if (k == 1) {
            return head;
        }
        ListNode newHead = reverse(head.next, --k);
        newHead.next = head;
        return newHead.next;
    }
}

83. 删除排序链表中的重复元素

题目解析：直接遍历全链表，有重复删除即可。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 链表
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode res = head;
        while (head != null && head.next != null) {
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }
        return res;
    }
}

92. 反转链表 II

题目解析：用递归反转指定范围里的节点，再连接进主链表即可。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 递归
 */
class Solution {

    ListNode successor = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {

        if (left == 1) {
            return helper(head, right);
        }

        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    public ListNode helper(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }

        ListNode last = helper(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

155. 最小栈

题目解析：用链表，每个节点存储时，把该节点情况下最小值也存进去即可。
代码如下：

/**
 * 链表
 */
class MinStack {
    private Node head;
    
    public void push(int x) {
        if(head == null) 
            head = new Node(x, x);
        else 
            head = new Node(x, Math.min(x, head.min), head);
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
    
    private class Node {
        int val;
        int min;
        Node next;
        
        private Node(int val, int min) {
            this(val, min, null);
        }
        
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

203. 移除链表元素

题目解析：虚拟头节点，用虚拟头节点的好处是，防止第一个节点也是删除的节点的情况，且方便返回头节点。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 
/**
 * 链表
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode header = new ListNode(-1);
        header.next = head;
        ListNode cur = header;
        while(cur.next != null){
            // 当前节点下一节点为删除节点时，直接删除掉下一节点
            if(cur.next.val == val ){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return header.next;
    }
}

206. 反转链表

题目解析：虚拟头节点，用虚拟头节点方便返回头节点。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 
 /**
  * 链表
  */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        if(head == null){
            return null;
        }

        ListNode dummyHead = new ListNode(-1);
        while(head != null){
            ListNode temp = dummyHead.next;
            dummyHead.next = new ListNode(head.val);
            dummyHead.next.next = temp;
            head = head.next;
        }
        return dummyHead.next;
    }
}

237. 删除链表中的节点

题目解析：依次用后一节点的值代替当前节点的值。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

/**
 * 链表
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 今当前节点值为下一节点值
        node.val = node.next.val;
        // 申请下一节点
        ListNode nextNode = node.next;
        // 判断依次替换之后的节点
        while (nextNode.next != null) {
            nextNode.val = nextNode.next.val;
            node = nextNode;
            nextNode = nextNode.next;
        }
        // 删除最后一个节点
        node.next = null;
    }
}

回到首页

刷 leetcode 500+ 题的一些感受

下一篇

[xxxxx]