java单链表常用操作

概述、

数据结构与算法亘古不变的主题，链表也是面试常考的问题，特别是手写代码常常出现，将从以下方面做个小结

【链表个数】

【反转链表-循环】

【反转链表-递归】

【查找链表倒数第K个节点】

【查找链表中间节点】

【判断链表是否有环】

【从尾到头打印单链表-递归】

【从尾到头打印单链表-栈】

【由小到大合并有序单链表-循环】

【由小到大合并有序单链表-递归】

通常在java中这样定义单链表结构

class Node{
    int value;
    Node next;
    public Node(int n){
        this.value = n;
        this.next = null;	
    }
}

1、链表个数

这个比较简单，不再赘述

// 求单链表的结点个数
public int getListLen(Node head) {
    int len = 0;
    while (head != null) {
        len++;
        head = head.next;
    }
    return len;
}

2、反转链表-循环

采用双指针，主要是4行代码，其中2,3俩行完成指针反转，1,4主要是保持head往下指

// 反转单链表(循环)
public Node reverseList(Node head) {
    // 安全性检查
    if (head == null || head.next == null)
        return head;
    Node pre = null;
    Node temp = null;
    while (head != null) {
        // 以下1234均指以下四行代码
        temp = head.next;// 与第4行对应完成头结点移动
        head.next = pre;// 与第3行对应完成反转
        pre = head;// 与第2行对应完成反转
        head = temp;// 与第1行对应完成头结点移动
    }
    return pre;
}

3、反转链表-递归

// 将单链表反转,递归
public static Node reverseListRec(Node head) {
    if (head == null || head.next == null)
        return head;
    Node reHead = reverseListRec(head.next);
    head.next.next = head;
    head.next = null;
    return reHead;
}

4、查找链表倒数第K个节点

双指针法，不多解释

// 查找单链表倒数第K个结点 双指针法
public Node reKNode(Node head, int k) {
    if (head == null)
        return head;
    int len = getListLen(head);
    if (k > len)
        return null;
    Node targetK = head;
    Node nextK = head;
    // 先走到K个位置
    for (int i = 0; i < k; i++) {
        nextK = nextK.next;
    }
    // 再和头结点一起走，nextk走到结尾，此时targetk为倒数第K个节点
    while (nextK != null) {
        nextK = nextK.next;
        targetK = targetK.next;
    }
    return targetK;
}

5、查找链表中间节点

快慢指针，不多解释

public Node getMid(Node head) {
    // 类似的快慢指针法
    // 安全性检查
    if (head == null || head.next == null)
        return head;
    Node target = head;
    Node temp = head;
    while (temp != null && temp.next != null) {
        target = target.next;
        temp = temp.next.next;
    }
    return target;
}

6、判断链表是否有环

主要还是快慢指针，如果快的指针能够追上慢指针则有环

// 判断一个单链表中是否有环,快慢指针
public boolean hasCycle(Node head) {
    boolean flag = false;
    Node p1 = head;
    Node p2 = head;
    while (p1 != null && p2 != null) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p2 == p1) {
            flag = true;
            break;
        }
    }
    return flag;
}

7、从尾到头打印单链表-递归

// 从尾到头打印单链表(递归)
public void reList1(Node head) {
    // 安全性检查
    if (head == null)
        return;
    else {
        reList1(head.next);
        System.out.println(head.value);
    }

}

8、从尾到头打印单链表-栈

利用栈FILO的性质，先存储节点然后输出每个栈的节点值

// 从尾到头打印单链表（栈）
public void reList2(Node head) {
    Stack<Node> s = new Stack<Node>();
    while (head != null) {
        s.push(head);
        head = head.next;
    }
    while (!s.isEmpty()) {
        System.out.println(s.pop().value);
    }
}

9、由小到大合并有序单链表-循环

// 由小到大合并俩个有序的单链表(循环)
public Node mergeSort1(Node head1, Node head2) {
    // 安全性检查
    if (head1 == null)
        return head2;
    if (head2 == null)
        return head1;
    // 新建合并节点
    Node target = null;
    // 确定第一个元素的节点
    if (head1.value > head2.value) {
        target = head2;
        head2 = head2.next;
    } else {
        target = head1;
        head1 = head1.next;
    }
    target.next = null;
    // 开始合并
    Node mergeHead = target;
    while (head1 != null && head2 != null) {
        // 当两个链表都不为空
        if (head1.value > head2.value) {
            target.next = head2;
            head2 = head2.next;
        } else {
            target.next = head1;
            head1 = head1.next;
        }
        target = target.next;
        target.next = null;
    }
    if (head1 == null)
        target.next = head2;
    else
        target.next = head1;
    return mergeHead;

}

10、由小到大合并有序单链表-递归

// 由小到大合并俩个有序的单链表(递归)
public Node mergeSort2(Node head1, Node head2) {
    if (head1 == null)
        return head2;
    if (head2 == null)
        return head1;
    if (head1.value > head2.value) {
        head2.next = mergeSort2(head2.next, head1);
        return head2;
    } else {
        head1.next = mergeSort2(head1.next, head2);
        return head1;
    }
}