java单链表常用操作-阿里云开发者社区

总结提高，与君共勉

概述、

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

【链表个数】

【反转链表-循环】

【反转链表-递归】

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

【查找链表中间节点】

【判断链表是否有环】

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

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

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

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

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">class Node{  
    int value;  
    Node next;  
    public Node(int n){  
        this.value = n;  
        this.next = null;     
    }  
}  
</span>  

1、链表个数

这个比较简单，不再赘述

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">    // 求单链表的结点个数  
    public int getListLen(Node head) {  
        int len = 0;  
        while (head != null) {  
            len++;  
            head = head.next;  
        }  
        return len;  
    }</span>  

2、反转链表-循环

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 反转单链表(循环)  
    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;  
    }</span>  

3、反转链表-递归

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 将单链表反转,递归  
    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;  
    }</span>  

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

双指针法，不多解释

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 查找单链表倒数第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;  
    }</span>  

5、查找链表中间节点

快慢指针，不多解释

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">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;  
    }</span>  

6、判断链表是否有环

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 判断一个单链表中是否有环,快慢指针  
    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;  
    }</span>  

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表(递归)  
    public void reList1(Node head) {  
        // 安全性检查  
        if (head == null)  
            return;  
        else {  
            reList1(head.next);  
            System.out.println(head.value);  
        }  
  
    }</span>  

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

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 从尾到头打印单链表（栈）  
    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);  
        }  
    }</span>  

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">    // 由小到大合并俩个有序的单链表(循环)  
    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;  
  
    }</span>  

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

[java]view plain copy
<span style="font-family:Microsoft YaHei;font-size:14px;">// 由小到大合并俩个有序的单链表(递归)  
    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;  
        }  
    }</span>  

转载：http://blog.csdn.net/xsf50717/article/details/47375437