[数据结构与算法]单链表的简单操作

1、链表的翻转

//翻转单链表
    public ListNode reverseList(){
        ListNode cur = this.head;//记录当前需要翻转的节点
        ListNode prev = null;//记录当前需要翻转节点的前驱
        ListNode curNext = null;//记录需要翻转节点的下一项
        while(cur != null){
            curNext = cur.next;//记录需要翻转节点的下一项
            cur.next = prev;//将需要翻转的节点的next指向前一节点
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addLast(1);
        myLinkedList1.addLast(13);
        myLinkedList1.addLast(18);
        myLinkedList1.addLast(25);
        myLinkedList1.addLast(30);
       
        myLinkedList1.show();
        ListNode newHead = myLinkedList1.reverseList();
        myLinkedList1.show2(newHead);
    }
}

?

2、返回链表的中间节点?

只遍历一遍单链表 （双指针）? ?原理：同时同地点出发速度快二倍路程快二倍

public ListNode middleNode(){
        ListNode fast = this.head;
        ListNode slow = this.head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;//fast 每次走两步
            slow = slow.next;//slow走一步
        }
        return slow;
    }

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addLast(1);
        myLinkedList1.addLast(13);
        myLinkedList1.addLast(18);
        myLinkedList1.addLast(25);
        myLinkedList1.addLast(30);
       
        myLinkedList1.show();
        System.out.println(myLinkedList1.middleNode().val);
    }
}

?

3、找到倒数第k项

双指针? 原理：倒数第一项与倒数第k项差k-1步，让fast先走k-1步，然后fast与slow同时走，当fast走到最后一项时，slow就在倒数第k项

//找到倒数第k项
    public ListNode findKToTail(int k){
        if (k<0||head==null){
            return null;
        }
        ListNode fast = kSubOne(k);
        if (fast == null){
            System.out.println("k位置不合法");
            return null;
        }
        ListNode slow = this.head;
        while(fast.next!=null){//fast停在最后一个位置不能走了
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //fast先走第k-1步
    public ListNode kSubOne(int k){
        ListNode cur = this.head;
        while(k-1!=0){
            cur = cur.next;
            if (cur==null){
                System.out.println("没有这个节点");
                return null;
            }
            k--;
        }
        return cur;
    }

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addLast(1);
        myLinkedList1.addLast(13);
        myLinkedList1.addLast(18);
        myLinkedList1.addLast(25);
        myLinkedList1.addLast(30);
       
        myLinkedList1.show();
        System.out.println(myLinkedList1.findKToTail(2).val);
    }
}

?