算法训练营day03 | {203. 移除链表元素, 707.设计链表, 206.反转链表}

第二章链表-part01，知识点为虚拟头结点、双指针原地反转链表、递归写法。

203. 移除链表元素

• 题目链接：203.移除链表元素
• 文档讲解：代码随想录–203移除链表元素
• 视频讲解：手把手带你学会操作链表 | LeetCode：203.移除链表元素
• 状态：简单的单链表删除

1.1 看到题目的想法

加上虚拟的头结点，统一任意位置结点的删除操作，比较简单，实现如下：

▶

AC解法

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode p = preHead.next;
        ListNode pre = preHead;
        while (p != null) {
            if (val == p.val) {
                // 删除结点
                pre.next = p.next;
            } else {
                pre = p;
            }
            p = p.next;
        }

        return preHead.next;
    }
}

1.2 看完代码随想录的想法

• 设置虚拟头结点的写法，变量定义取名cur和dummy感觉挺好的。

707. 设计链表

• 题目链接：707.设计链表
• 文档讲解：代码随想录–707.设计链表
• 视频讲解：帮你把链表操作学个通透！LeetCode：707.设计链表
• 状态：写了一种单链表的MyLinkedList，挺简单。

2.1 解题过程

注意第一次提交尾插法方法没有考虑到链表本身为空时，会有空指针异常。代码如下：

▶

AC解法

package cn.leetcode.list;

/**
 * 设计单链表
 */
public class MyLinkedList {

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode listHead;  // 链表虚拟头结点
    private int size;

    public MyLinkedList() {
        listHead = new ListNode(0);
        size = 0;
    }

    /**
     * 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
     * @param index 链表下标
     * @return
     */
    public int get(int index) {
        ListNode p = listHead.next;
        if(index < 0 || index >= size) return -1;
        for (int i = 0; i <= index - 1; i++) {
            p = p.next;
        }
        return p.val;
    }

    /**
     * 头插法
     * @param val
     */
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = listHead.next;
        listHead.next = newNode;
        size++; // 更新size
    }

    /**
     * 尾插法
     * @param val
     */
    public void addAtTail(int val) {
        ListNode newNode = new ListNode(val);
        ListNode p = listHead;  // 注意null pointer
        while(p.next != null) {
            p = p.next;
        }
        p.next = newNode;
        newNode.next = null;
        size++;
    }

    /**
     * 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如
     * 果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
     * 如果 index 比长度更大，该节点将 不会插入 到链表中。
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        if(index == size) {
            addAtTail(val);
        } else if (index > size) {
            return;
        } else {
            ListNode newNode = new ListNode(val);
            ListNode p = listHead.next;
            ListNode pre = listHead;
            for (int i = 0; i <= index - 1 ; i++) {
                pre = p;
                p = p.next;
            }
            // 执行插入操作
            newNode.next = pre.next;
            pre.next = newNode;
            size++;
        }
    }

    /**
     * 如果下标有效，则删除链表中下标为 index 的节点。
     * @param index
     */
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) return;
        ListNode p = listHead.next;
        ListNode pre = listHead;
        for (int i = 0; i <= index - 1 ; i++) {
            pre = p;
            p = p.next;
        }
        // 执行删除操作
        pre.next = p.next;
        size--;
    }
}

206. 反转链表

• 题目链接：206.反转链表
• 文档讲解：代码随想录–206.反转链表
• 视频讲解：帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法
• 状态：开了新的连表头，头插法解出来的。

3.1 看完视频讲解的想法

• 双指针法，原地反转的做法真妙啊，值得学习。
• 对照双指针方法写出递归解法。动画如下：
  
  两个版本的代码如下：
  ▶

  AC解法

  package cn.leetcode.list;
  
  public class ReverseList {
      /**
       * 双指针写法，原地反转
       * @param head
       * @return
       */
      public ListNode reverseList(ListNode head) {
          ListNode cur = head;
          ListNode pre = null;
          while(cur != null) {
              ListNode temp = cur.next;
              cur.next = pre;
              pre = cur;
              cur = temp;
          }
          return pre;
      }
  
      /**
       * 递归写法主函数
       * @param head
       * @return
       */
      public ListNode reverseListV2(ListNode head) {
          return reverse(head, null);
      }
  
      public ListNode reverse(ListNode cur, ListNode pre) {
          if(cur == null) return pre;
          ListNode temp = cur.next;
          cur.next = pre;
          return reverse(temp, cur);
      }
  
  }