链表

基础介绍

以结点的方式来存储，通过指针串联起来
每个结点包含数据域，指针域：指向下一个结点
各个结点不一定是连续存放的
分类：有头结点 和 无头结点

链表类型

单链表
双链表
- 一个结点有两个指针，分别指向上下两个结点
循环链表
- 首尾相连，解决约瑟夫环问题

基础操作

显示结点
添加结点
指定位置插入结点
- 找到位置
- 新结点.next = temp.next
- 将temp.next = 新的结点
修改第k个结点
删除某个结点
- temp.next = temp.next.next

性能分析

面试题

求单链表的有效结点个数

//获取到单链表的结点个数（如果是带头结点的链表，不统计头结点）
public static int getLength(Node head) {
    if (head.next == null) {
        return 0;
    }
    int length = 0;
    Node cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

查找单链表中倒数第k个结点（新浪）

先获取链表的length
之后从链表第一个开始遍历（length-index）个，就可以得到
如果找到了，返回该结点，否则返回null

//查找倒数第k个结点
public static Node findLastIndexNode(Node head, int index) {
    //判断如果链表为空，返回null
    if (head.next == null) {
        return null;
    }
    int length = getLength(head);
    //对length进行较验
    if (index <= 0 || index > length) {
        return null;
    }
    //定义辅助变量，for循环定位到倒数的index
    Node cur = head.next;
    for (int i = 0; i < length - index; i++) {
        cur = cur.next;
    }
    return cur;
}

单链表的反转

定义一个结点revereHead = new Node();
从头到尾遍历原来的链表，就将其取出，并放在revereHead的最前端
最后head.next = reverseHead.next

//反转单链表
public static void reverseList(Node head) {
    if (head.next == null || head.next.next == null) {
        return;
    }

    Node cur = head.next;
    //指向当前结点【cur】的下一个结点
    Node next = null;
    Node reverseHead = new Node(1);
    //从头遍历原来的链表，每经过一个结点，就将其取出，放到reverseHead的最前端
    while (cur != null) {
        next = cur.next; //暂时保存当前结点的下一个结点，后续使用
        cur.next = reverseHead.next; //将cur的下一个结点指向reverseHead的最前端
        reverseHead.next = cur; //将cur连接到reverseHead上
        cur = next; //让cur后移
    }
    //将head的next连接reverseHead.next
    head.next = reverseHead.next;
}

从尾到头打印单链表

方案1：反转链表，遍历打印（不建议，会改变单链表的结构）
方案2：利用栈，将各个结点压入栈中，利用先进后出的特点，实现逆序打印。

//反向打印单链表，不破环原结构
public static void reversePrint(Node head) {
    if (head.next == null) {
        return;
    }
    Stack<Node> stack = new Stack<Node>();
    Node cur = head.next;
    //将所有结点压入栈
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    while (stack.size() > 0) {
        System.out.printf("%d\t", stack.pop());
    }
}

合并两个有序的单链表，合并后依然有序

//合并两个有序链表，合并后依然有序
public static Node mergeList(Node head1, Node head2) {
    Node cur1 = head1.next;
    Node cur2 = head2.next;
    Node head = new Node(0);
    Node cur = head;
    while (cur1 != null & cur2 != null) {
        if (cur1.value <= cur2.value) {
            cur.next = cur1; //将结点连接到新链表
            cur = cur.next; //cur后移一位
            cur1 = cur1.next; //cur1后移一位
        } else {
            cur.next = cur2; //将结点连接到新链表
            cur = cur.next; //cur后移一位
            cur2 = cur2.next; //cur2后移一位
        }
    }
    if (cur1 != null) {
        cur.next = cur1;
    } else if (cur2 != null) {
        cur.next = cur2;
    }
    return head;
}

改造

双向链表

结构
- 增加一个pre指针，指向前一个结点

方法

添加
- 先走在链表最后，temp.next = new Node()
- 然后newNode.pre = temp
修改：不变

插入：找到插入位置的前一个结点,分两种情况

public void addByOrder(DoubleNode node) {
    if (isEmpty()) {
        head.next = node;
        node.pre = head;
        return;
    }
    DoubleNode temp = head.next;
    while (temp.next != null) {
        if (node.value < temp.next.value) {
            break;
        }
        temp = temp.next;
    }
  //判断下个结点是否为null
    if (temp.next != null) {
        temp.next.pre = node;
        node.next = temp.next;
    }
    temp.next = node;
    node.pre = temp;
}

删除
- 找到删除的结点temp
- temp.pre.next = temp.next
- Temp.next.pre = temp.pre

单项环形链表（约瑟夫环）

构建一个单向环形链表
- 先创建第一个结点，让this指向该结点，并形成环形
- 后面构建的每一个新的结点，加入已有的环形链表
遍历环形链表
- 先让辅助指针，指向first结点
- 通过while循环遍历
- temp.next == first 结束

class CircleSingleLinkedList {
    private JNode first = null;

    //给定一个数量，创建一个环形链表
    public void addNodes(int nums) {
        if (nums < 1) {
            System.out.println("nums值不正确");
            return;
        }
        JNode cur = null;
        for (int i = 1; i <= nums; i++) {
            JNode jNode = new JNode(i);
            if (i == 1) {
                first = jNode;
                first.setNext(jNode); //构成环
                cur = first; //cur指向第一个结点
            } else {
                cur.setNext(jNode);
                jNode.setNext(first);
                cur = jNode;
            }
        }
    }
		//是否为空
    public boolean isEmpty() {
        return first == null;
    }

    //遍历环形链表
    public void showList() {
        if (isEmpty()) {
            System.out.println("链表为空");
        }
        JNode cur = first;
        while (true) {
            System.out.printf("%d\t", cur.getValue());
            if (cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
    }
}

class JNode {
    private int value;
    private JNode next;

    public JNode(int val) {
        value = val;
    }
    public JNode getNext() {
        return next;
    }
    public void setNext(JNode next) {
        this.next = next;
    }
    public int getValue() {
        return value;
    }
    public void setValue(int val) {
        this.value = val;
    }
}

给定一个数，生成输出顺序

参数
- 从哪个结点开始：start
- 间隔是多少：countNum
- 结点的个数是多少：nums
思路
- 辅助指针helper，事先指向环形链表的最后一个结点
- 输出之前。先让first和helper移动k-1次
- 结点输出时，将first和helper同时移动m-1次，可以使该结点移除出链表
- 直到链表中剩下一个结点，循环结束，helper == first

链表 #

基础介绍 #

链表类型 #

基础操作 #

性能分析 #

面试题 #

改造 #

双向链表 #

单项环形链表（约瑟夫环） #

链表

基础介绍

链表类型

基础操作

性能分析

面试题

改造

双向链表

单项环形链表（约瑟夫环）