链表笔记

定义

节点的定义：

可以用任意一组储存单元来储存数据元素（储存单元可以是不联系的）
除了储存每个数据元素外，还必须储存指示其直接后续元素的信息
这两部分的信息租车的数据元素的储存印象为节点

链表：

多个节点在一块被称为链表

单链表：

当节点只包含其后继节点信息的链表为单链表

头结点：

链表的第一个节点为头结点

单链表中有头节点：

有头节点是指单链表中存在第一个节点，若链表为空，则指向空，若链表不为空则指向第一个元素节点的储存位置

单链表中无头节点：

无头节点是指单链表中不存在指向第一个元素节点储存位置的节点，若链表为空，则第一个节点为空

有头节点的作用：

1当链表的任何节点之前插入或删除节点时，都需要修改前一个节点的指向，因为单链表所有节点都有前驱节点。
若链表没有头结点，则元素节第一节点没有前驱节点，修改时操作复杂。
2对于空链表费空链表所有的头指针都不为空

举例

将单链表h-1-2-3-4-5-6-7 逆序 变为h-7-6-5-4-3-2-1
链表对象LNode

/**
 * 链表对象
 * 
 * @author xus
 *
 */
public class LNode {
    int data;//链表中存在的值
    LNode next;//链表中存在的指向，java中用引用
}

public class ReverseOrder {
    /*
     * 创建一个单链表，并逆序
     */

    public static void main(String[] args) {
        LNode head = new LNode();//创建一个链表对象
        head.next = null;//将链表头对象的指向先设为空
        LNode tmp = null;//临时链表节点指向，
        LNode cur = head;//真正的链表节点对象
        for (int i = 0; i < 8; i++) {//创建7个节点
            tmp = new LNode();
            tmp.data = i;//将临时的值设为i
            tmp.next = null;//先将零时节点指向指空
            cur.next = tmp;//将上一个节点的指向指为本次创建的节点
            cur = tmp;指定本次节点
        }
        System.out.println("逆序前");
        
        for(cur=head.next;cur!=null;cur=cur.next) {
            System.out.println(cur.data+"");
        }
        System.out.println("\n逆序后");
        Reverse(head);
        for(cur=head.next;cur!=null;cur=cur.next) {
            System.out.println(cur.data+"");
        }
    }
/**
*这里将有序链表逆序
*/
    public static void Reverse(LNode head) {
        if (head == null || head.next == null)//若传进来的头为空则退出
            return;

        LNode pre = null;//上一个节点
        LNode cur = null;//指向节点
        LNode next = null;//下一个节点
        cur = head.next;//先将当前节点指向头结点
        next = cur.next;//将下一个节点指向头结点的下一个节点
        cur.next = null;//当前节点指空
        pre = cur;//将上一个节点变成当前节点
        cur = next;//将当前节点变成下个节点
//遍历所有节点，让当前的下一个节点指向上一个节点
        while (cur.next!= null) {//如果当前节点没有指向节点，则说明该节点为最后一个节点
            next = cur.next;//下一个节点指向当前节点的下一个节点
            cur.next = pre;//将当前下一个指向节点指向上一个节点
            pre = cur;//让上一个节点变成当前节点
            cur = cur.next;//让per节点变成当前的下一个节点
            cur = next;//让当前节点变成下个节点继续循环
        }
        cur.next = pre;//让最后一个节点指向倒数第二个节点
        head.next = cur;//让链表头指向最后一个节点
    }
}

这种是对所有链表进行遍历，所以时间复杂度O（N），N=链表长度，而且对原链表进行了破坏