单链表

遍历索引

查找倒数第 k 个节点

设置两个指针 p1,p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        //先求得链表的尺寸，赋值给size
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        //获取next实例域size-k次，即可得到倒数第k个结点(从1开始计数)
        for (int i = 0; i < size - k; i++) {
            head = head.next;
        }
        return head;
    }
}

反转链表

public void reverse() {

    //指向当前正在操作的节点
    Node current = first;

    //指向当前节点的前一个节点
    Node prevHead = null;

    while (current != null) {

        //获取当前节点指向的下一个节点
        Node next = current.next;

        //此时才将当前节点的后置节点设置为前一个节点完成翻转
        current.next = prevHead;

        //如果下一个节点为null,即原来的尾节点,现在的头节点
        if (next == null) {
            this.first = current;
        }

        //将后置节点设置为当前节点
        prevHead = current;

        //使指针移动到下一个节点
        current = next;
    }
}

最近更新于 0001-01-01