[数据结构与算法]Java实现单链表+链表反转

Java实现单链表+链表反转

Java实现单链表

import java.util.Iterator;

/**
 * 单链表
 */
public class LinkList<T> implements Iterable<T> {
    private Node head;//记录头节点
    private int N;//记录链表长度

    public LinkList() {
        //初始化链表：头节点为null，链表长度为0
        this.head = new Node(null, null);
        this.N = 0;
    }

    public void clear() {
        this.head.next = null;//头节点的next = null
        this.N = 0;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int length() {
        return N;
    }

    public T get(int i) {
        if (i < 0 || i >= N) {
            throw new RuntimeException("位置不合法");
        }
        Node node = head.next;
        //通过循环，从头结点开始往后找，依次找i次，就可以找到第i个元素
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return (T) node.item;
    }

    public void insert(T t) {

        //生成一个新的结点
        /*Node node = new Node(t,null);//插入单链表头部--前插法
        Node node1 = head.next;
        head.next = node;
        node.next = node1;
        N++;*/
        //后插法
        Node node = new Node(t, null);
        //找到当前链表最后一个结点
        Node node1 = head;
        while (node1.next != null) {
            node1 = node1.next;
        }
        node1.next = node;
        N++;
    }

    //在第i个元素之前插入t
    public void insert(int i, T t) {
        if (i < 0 || i >= N) {
            throw new RuntimeException("位置不合法");
        }
        Node preNode = head;
        //获得第i-1个结点
        for (int index = 0; index < i - 1; index++) {
            preNode = preNode.next;
        }
        Node curr = preNode.next;
        Node newNode = new Node(t, curr);
        preNode.next = newNode;

        N++;

    }

    public T remove(int i) {
        if (i < 0 || i >= N) {
            throw new RuntimeException("位置不合法");
        }
        //1.获得i-1处的结点
        Node node = head;
        for (int index = 0; index < i - 1; index++) {
            node = node.next;
        }
        Node curr = node.next;//第i个结点
        node.next = curr.next;
        N--;
        return (T) curr;
    }

    public int indexOf(T t) {
        Node node = head;
        //循环内部node.next != null; 要记忆一下
        for (int index = 0; node.next != null; index++) {
            node = node.next;
            if (node.item == t) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public Iterator<T> iterator() {
        return new SIterator<T>();
    }

    private class SIterator<T> implements Iterator<T> {
        private Node node;

        public SIterator() {
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public T next() {
            node = node.next;
            return (T) node.item;
        }
    }

    private class Node {
        //存储元素
        public T item;
        //指向下一个结点
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

链表反转

需求：

原链表中数据为：1->2->3->4

反转后链表中元素为：4->3->2->1

实现方式：使用递归完成反转，递归反转就是从原链表的第一个存储数据的结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕了。

    //单链表的反转【面试】
    public void reverse(){
        if (N==0){
            return;//链表为空，不需要反转
        }
        reverse(head.next);//从链表第一个结点开始反转
    }
    //使用递归，实现反转
    public Node reverse(Node curr){
        //已经到了最后一个元素
        if (curr.next==null){
            //反转后，头结点指向原链表中的最后一个结点
            head.next = curr;
            return curr;
        }
        //当前节点的上一个结点
        Node pre = reverse(curr.next);
        pre.next = curr;
        curr.next = null;
        return curr;
    }