【LeetCode】二、链表相关：移除与反转链表

1、链表结构

和数组不同，此时不需要连续的内存空间，如下为单端链表，无pre指针

时间复杂度：

和数组相反，访问元素时不能再直接计算出对应下标的内存地址，时间复杂度变为O(N)，但插入和删除不用再前移或后移受影响的全部元素，而是只需要修改对应位置的next指针指向，因此单这个操作的时间复杂度为O(1)，但其实插入和删除前得先从头开始遍历到对应位置的元素，因此，时间复杂度整体为O(n)，适用于读少写多的场景

2、leetcode203：移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。

思路：

• 传入起始头节点，在没到尾节点之前（next为null即到尾节点，node为null说明尾节点也处理完了），一直head=head.next往下遍历

• 如果不满足head.val==val，则继续往下遍历

• 满足则让当前节点head的前一个节点指向head.next，完成删除，但当前为单向链表，获取不到前一个节点，因此需要维护一个pre node的值，记录遍历到的当前节点的head的前一个节点，以便进行删除操作

• 此外，要求最后返回新的头节点，只靠一直往下移动的pre和head，遍历完后，无法获得头节点信息（单向链表），因此还要加一个虚拟节点dummy（位置在传入的head的前一个节点），dummy的next等于传入的头节点，dummy的val则随便给，反正用不到
  
  

• 刚开始时，虚拟节点赋值给pre，如此，即使传入的头节点就符合要求被删了，那pre的next指向第二个节点，也即虚拟节点的next指向第二个节点，如此能保证dummy.next始终为新的头节点

• 反之，传入的头节点不被删，那pre和head往下走，判断下一个节点，此时就不关虚拟节点的事了，它只是记录了头节点信息

Java实现：

//链表节点类
public class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

移除的实现：

public class P203 {

    public static ListNode removeElements(ListNode head, int val) {
        ListNode dummyNode = new ListNode(0, head);
        // 刚开始时，head节点的前一个节点为虚拟节点dummyNode
        ListNode prev = dummyNode;
        while (head != null && head.next != null) {
            if (head.val == val) {
                prev.next = head.next;
                //head再向下移一位
                head = head.next;
            } else {
                prev = head;
                head = head.next;
            }
        }
        return dummyNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

测试：

public class P203 {

    public static void main(String[] args) {
        ListNode tailNode = new ListNode(1, null);
        ListNode node4 = new ListNode(2, tailNode);
        ListNode node3 = new ListNode(2, node4);
        ListNode node2 = new ListNode(1, node3);
        ListNode node1 = new ListNode(0, node2);
        ListNode head = new ListNode(9, node1);
        ListNode listNode = removeElements(head, 9);
        System.out.println(listNode.val);
        System.out.println(listNode.next);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、leetcode206：反转链表

思路：如上，先把2移动到1的前面，再把3移动到2的前面，再把4移动到3的前面

//链表节点类
public class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

倒装函数的实现：

public class P206 {

    public static ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        while (head != null && head.next != null) {
            ListNode moveNode = head.next;
            ListNode currentHeadNode = dummy.next;
            //虚拟节点改为指向要移动的节点
            dummy.next = moveNode;

            //原来的头节点改为指向下一个待移动的节点
            head.next = head.next.next;

            //要移动的节点改为指向移动后的第一个节点（虚拟节点的下一个节点）
            moveNode.next = currentHeadNode;

        }
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

测试：

public class P206 {

    public static void main(String[] args) {
        ListNode tailNode = new ListNode(6, null);
        ListNode node4 = new ListNode(5, tailNode);
        ListNode node3 = new ListNode(4, node4);
        ListNode node2 = new ListNode(3, node3);
        ListNode node1 = new ListNode(2, node2);
        ListNode head = new ListNode(1, node1);
        ListNode listNode = reverse(head);
        System.out.println(listNode.val);
        System.out.println(listNode.next);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15