数据结构-链表和递归

使用链表解决问题

leetcode 203号问题

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

给定的节点

public class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }
}

不使用虚拟头结点

如果链表头部是需要删除的元素, 直接进行删除, 直到整个链表删除完或者链表头不是需要删除的元素为止; 然后开始删除头结点后面需要删除的元素

class Solution {
    public ListNode removeElements(ListNode head, int val) {

        while(head != null && head.val == val){
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }

        if(head == null)
            return head;

        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val) {
                ListNode delNode = prev.next;
                prev.next = delNode.next;
                delNode.next = null;
            }
            else
                prev = prev.next;
        }

        return head;
    }
}

另一种方法是既然头部是需要删除的节点, 就直接跳过去, 不去管它, 那么整个链表剩下的就是头结点不需要删除的了

    public ListNode removeElements(ListNode head, int val) {

        while(head != null && head.val == val)
            head = head.next;

        if(head == null)
            return head;

        ListNode prev = head;
        while(prev.next != null){
            if(prev.next.val == val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }

        return head;
    }

使用虚拟头结点

public ListNode removeElements(ListNode head, int val) {

        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        while(prev.next != null){
            if(prev.next.val == val)
                prev.next = prev.next.next;
            else
                prev = prev.next;
        }

        return dummyHead.next;
    }

递归

本质上是将原来的问题转化为更小的同一问题

    public ListNode removeElements(ListNode head, int val) {
        // 终止条件, 节点为空
        if(head == null)
            return head;

        // res 是头结点后面的不包含val的链表
        ListNode res = removeElements(head.next, val);

        // 最后判断头结点是否是需要删除的节点
        if(head.val == val)
            return res;
        else{
            head.next = res;
            return head;
        }
    }

化简

    public ListNode removeElements(ListNode head, int val) {

        if(head == null)
            return head;

        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }

其他结构的链表

双向链表

在双向链表中, 每个节点都有两个指针, 一个指向下一个节点, 一个指向前一个节点

image

//                      tail
//                       ↓
//  ⬜⇆⬜⇆⬜⇆⬜⇆⬜⇆⬜→null
//   ↑
//  head
class Node{
    E e;
    Node next, prev;
}

循环链表

循环链表的尾结点指向的是头结点

image

class Node{
    E e;
    Node next, prev;
}

数组链表

使用数组来实现链表, 存储的是元素和下一个节点的下标

image

class Node{
    E e;
    int index;
}

完整代码