链表

单链表 双向链表

特点

• 插入和删除，时间复杂度O(1)
• 查找，时间复杂度平均O(n)

应用场景

• 改善插入删除时间复杂度
• 不知道有多少元素，当有新元素就插入到末尾

实例

反转链表

input : 1->2->3->4->5->NULL
output : 5->4->3->2->1->NULL

双指针迭代

    public static ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            //记录当前节点的下一个节点
            ListNode temp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = temp;
        }
        return pre;
    }

双指针较简单，且容易理解

递归

递归较难一些，详细理解看注释。

    public static ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if (head == null || head.next == null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

两两交换链表中的节点

input : 1->2->3->4->5->NULL
output : 2->1->4->3->1->NULL

使用stack实现

 public static ListNode swapPairs(ListNode head) {
        //过滤掉不用转换的逻辑
        if (head == null || head.next == null) {
            return head;
        }
        //用栈存储
        Stack<ListNode> stack = new Stack<>();
        //创建一个特殊节点
        ListNode r = new ListNode();
        //将当前节点赋值head
        ListNode cur = head;
        //缓存下r节点，因为后面会移动r节点
        head = r;
        while (cur != null && cur.next != null) {
            stack.add(cur);
            stack.add(cur.next);
            //移动两位
            cur = cur.next.next;
            //第一次循环时，取出2，将r.next赋值2
            r.next = stack.pop();
            //将r变成2
            r = r.next;
            //第一次循环时，取出1，将2.next赋值1
            r.next = stack.pop();
            //将r变成1,等待下次循环时，1指向4
            r = r.next;
        }
        //循环完以后，如果当前节点非空，说明为奇数个数，将最后一个节点cur赋值给r.next
        if (cur != null) {
            r.next = cur;
        } else {
            r.next = null;
        }
        return head.next;
    }

使用迭代实现

迭代实现，关键在于，第二轮指针操作，需要缓存上一轮的末尾节点，用来指向下一轮的交换后的头节点。

public static ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = new ListNode();
        p.next = head;
        ListNode a = p;
        ListNode b = p;
        ListNode t = p;
        //因为是两两替换，b是第二个节点，如果它的下下节点都有的话，就可以实现两两替换，否则就终止
        while (b != null && b.next != null && b.next.next != null) {
            //先将 a指向第一个节点
            a = b.next;
            //再将 b指向第二个节点
            b = b.next.next;
            //这里比较关键，因为在2->1, 4->3 过程中，需要将1->4,
            // 这样才能关联起来，这一步就是这个操作，
            // 第二轮时，b是4，下面将第一轮的a缓存给t就可以
            t.next = b;
            // 将a节点缓存给t
            t = a;
            // 第一轮将1指向3
            a.next = b.next;
            // 第一轮将2执行1 这步骤走完，链表变成 2->1->3->4
            b.next = a;
            // 然后将b改为1，执行下一轮 3->4 的替换
            b = a;
        }
        return p.next;
    }

递归实现

递归的关键，在于第二轮将1->4的逻辑，让每次递归都返回head的第二个节点，这样来实现。

 public static ListNode swapPairs2(ListNode head) {
        if (head == null || head.next == null) return head;
        // 第一次递归时，缓存temp = 2
        ListNode temp = head.next;
        // 该步骤是，将下次递归返回的节点赋值给本次的第一个节点，也就是将1->4
        head.next = swapPairs2(temp.next);
        // 第一次递归 2->1 第二次递归 4->3
        temp.next = head;
        // 第一次递归完返回2，第二次递归时返回4，返回4时，上面  head.next = swapPairs2(temp.next); 实现 1-> 4
        return temp;
    }

链表是否有环

利用Set

Set的原理其实就是元素不重复，如果有环，那么在遍历结束前，肯定能碰到相同的元素，这样来判断是否有环

    public static boolean hasCycle(ListNode head){
        Set<ListNode> s = new HashSet<>();
        while (head!=null){
            if(s.contains(head)){
                return true;
            }
            s.add(head);
            head = head.next;
        }
        return false;
    }

利用快慢指针

 public static boolean hasCycle1(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && slow != null) {
            if (fast == slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

总结

以上是链表中最常见的几个题型，对于这些基本的操作，一定要熟练。