欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《数据结构与算法之美》----常见的链表操作

程序员文章站 2022-05-19 19:19:22
...

目录

 

单链表反转

两个有序的链表合并

删除链表倒数第 n 个结点

循环链表----约瑟夫问题


单链表反转

 /**
     * 翻转链表
     * 
     * 1->2->3
     * 
     * @param head
     * @return
     */
    public static Node reverseList(Node head) {
        Node newHead = null; //可以理解为尾节点
        Node temp;
        while (head != null) {
            temp = head;  //       temp = 1             temp=2     
            head = head.next; //   head = 2             head=3
            temp.next = newHead; //1->null              2->1->null
            newHead = temp;//      1(newhead) -> null   2(newhead)->1->null
        }
        return newHead == null ? head : newHead;
    }

两个有序的链表合并

 /**
     * 合并两个有序链表
     * @param l1
     * @param l2
     * @return
     */
    public static Node mergeSortList(Node l1, Node l2) {
        Node head = new Node(-1);
        Node temp = head;
        while(l1 != null && l2 != null) {
            if(l1.data <= l2.data) {
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }else {
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if(l1 != null) {
            temp.next = l1;
        }
        if(l2 != null) {
            temp.next = l2;
        }
        temp = head;
        head = head.next;
        temp = null;

        return head;
    }

删除链表倒数第 n 个结点

 

/**
     * 删除链表的倒数第N个节点
     * @param head
     * @param n
     * @return
     */
    public Node removeNthFromEnd(Node head, int n) {

        Node slowNode = head;
        Node fastNode = head;

        for (int i = 0; i < n; i++) {
            fastNode = fastNode.next;
        }

        if (fastNode == null) { //倒数第N个节点即为头节点
            return slowNode.next;
        }

        while (fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }

        slowNode.next = slowNode.next.next; //删除

        return head;
    }

 

循环链表----约瑟夫问题

public static void count(int n){
        //数到3出局
        int k = 3;
        //头结点不存储数据(哨兵节点)
        Node head = new Node();
        Node cur = head;
        //循环构造这个链表
        for(int i=1;i<=n;i++){
            Node node = new Node(i);
            cur.next = node;
            cur = node;
        }
        //链表有数据的部分首尾相连形成一个环。
        cur.next = head.next;
        //统计开始的时候,刨去头结点,然后从第一个有数据的结点开始报数
        Node p = head.next;
        //循环退出的条件是最后只剩一个结点,也就是这个结点的下一个结点是它本身
        while(p.next!=p){
            //正常报数的遍历逻辑
            for(int i=1;i<k-1;i++){
                p = p.next;
            }
            //当数到3的时候,出局 此时p为出局的前一个节点
            System.out.print(p.next.data+"->");
            p.next = p.next.next;
            p = p.next;
        }
        //最后剩下的一个结点
        System.out.println("(left:"+p.data+")");
    }