算法（二）-单链表

一、概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

二、常见的单链表算法题

class Node {
    Node next;
    int value;

    public Node(int v) {
        value = v;
    }
}

public class test {
    // 构建链表
    public static Node getLinkedList() {
        Node head = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        Node node4 = new Node(5);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return head;
    }

    // 遍历链表并获取链表长度
    public static int printAndGetLength(Node head) {
        if (head == null) {
            return 0;
        }
        int len = 0;
        while (head != null) {
            len++;
            System.out.println(head.value);
            head = head.next;
        }
        return len;
    }

    // 1.逆序打印链表的值
    public static void revertPrint(Node head) {
        if (head != null) {
            revertPrint(head.next);
            System.out.println(head.value);
        }
    }

    // 2.获取链表倒数第K个结点的值
    public static int getRevertKNode(Node head, int k) {
        if (head == null) {
            return 0;
        }
        Node countHead = head;
        // 先获取链表长度
        int len = 0;
        while (countHead != null) {
            len++;
            countHead = countHead.next;
        }
        // 两个指针先都指向head，一个指针先移动len - k
        Node first = head;
        Node last = head;
        int i = 1;
        while (first != null && i < len - k) {
            i++;
            first = first.next;
        }
        // 然后两个指针同时走，当first指针到链表尾部时，last刚好对应倒数K结点位置
        while (first != null) {
            first = first.next;
            last = last.next;
        }
        return last.value;
    }

    // 3.判断链表是否有环
    public static boolean isLoop(Node head) {
        if (head == null) {
            return false;
        }

        // 使用快慢指针遍历，如果能相交，证明有环
        Node fast = head;
        Node slow = head;

        while (fast != null && slow != null && slow.next != null) {
            fast = fast.next;
            slow = slow.next.next;
            // 结点地址相同，表示相同结点
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    // 4.反转链表
    public static Node revertLinkedList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 通过递归模拟出栈过程，从尾到头依次调整指针指向
        Node newHead = revertLinkedList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    // 5.两个链表第一个公共结点
    public static Node getFirstCommonNode(Node first, Node second) {
        if (first == null && second == null) {
            return null;
        }
        // 先算长度
        Node firstP = first;
        Node secondP = second;
        int firstLen = 0;
        int secondLen = 0;
        while (firstP != null) {
            firstLen++;
            firstP = firstP.next;
        }
        while (secondP != null) {
            secondLen++;
            secondP = secondP.next;
        }

        Node fp = first;
        Node sp = second;
        // 长的链表先移动相差的位置
        if (firstLen > secondLen) {
            int i = 0;
            while (fp != null && i < firstLen - secondLen) {
                fp = fp.next;
                i++;
            }
        } else if (firstLen < secondLen) {
            int i = 0;
            while (sp != null && i < secondLen - firstLen) {
                sp = sp.next;
                i++;
            }
        }
        // 相同位置再一起移动，碰到第一个相同结点就是首个公共结点
        while (fp != null && sp != null) {
            if (fp.value == sp.value) {
                return fp;
            }
            fp = fp.next;
            sp = sp.next;
        }
        return null;
    }

    // 6.不等长链表逆序逐位相加
    public static Node revertMerge(Node first, Node second) {
        if (first == null && second == null) {
            return null;
        }
        // 先算长度
        Node firstP = first;
        Node secondP = second;
        int firstLen = 0;
        int secondLen = 0;
        while (firstP != null) {
            firstLen++;
            firstP = firstP.next;
        }
        while (secondP != null) {
            secondLen++;
            secondP = secondP.next;
        }
    
        Node fp = first;
        Node sp = second;
        // 长的链表先移动相差的位置
        if (firstLen > secondLen) {
            int i = 0;
            while (fp != null && i < firstLen - secondLen) {
                fp = fp.next;
                i++;
            }
            // 相同位置开始相加
            while (fp != null && sp != null) {
                fp.value = fp.value + sp.value;
                if(fp.next == null){
                    return first;
                }
                fp = fp.next;
                sp = sp.next;
            }
        } else if (firstLen < secondLen) {
            int i = 0;
            while (sp != null && i < secondLen - firstLen) {
                sp = sp.next;
                i++;
            }
            // 相同位置开始相加
            while (fp != null && sp != null) {
                sp.value = sp.value + fp.value;
                if(fp.next == null){
                    return second;
                }
                fp = fp.next;
                sp = sp.next;
            }
        } else {
            while (fp != null && sp != null) {
                fp.value = fp.value + sp.value;
                if(fp.next == null){
                    return first;
                }
                fp = fp.next;
                sp = sp.next;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ...
    }

}