Java教程

链表类(Linked List)

本文主要是介绍链表类(Linked List),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

链表类总结

  • 206. 反转链表

链表如何实现,如何遍历链表。链表可以保证头部尾部插入删除操作都是O(1),查找任意元素位置O(N),快慢指针和链表反转几乎是所有链表类问题的基础,尤其是反转链表,代码很短,建议直接背熟。

206. 反转链表

注:本题对递归又有了新的认知,前面学习递归的思想,更多的是不要用人脑去计算递归过程,而是用一种通用的办法直接得出答案,这种通用的过程称之为递推公式,后续部分已经完成了,只要关注第k个和第k+1个的逻辑即可!
那么本题新的认知是,递归是由递和归组成,递的过程反映的思想就是拆解成子问题的思想,归的过程就是在处理递推公式(完成指定功能),所谓的递归出口就是最小子问题的结果!
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 使用迭代法:充分定义好指针,这里需要三个指针,其中一个指针保存下一个节点信息,另外两个指针做好反转
        // 这种链表的迭代法一般画好图,做好记录节点信息,一步一步走就可以!
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null){
            // 若curr指针不空,记录下一个节点next
            ListNode next = cur.next;
            // cur指向前者
            cur.next = prev;
            // prev移动到cur
            prev = cur;
            // cur移动到下一个节点next
            cur = next;
        }
        // 最后返回最后一个节点:prev
        return prev;

    }
}

在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 使用递归方式解决
        // 最小子问题非递归出口
        if(  head == null ||head.next == null){
            return head;
        }
        // 递归的递过程,这里的p实际上是最后的一个节点
        ListNode p = reverseList(head.next);
        // 递归的归过程:递归函数,也就是递推公式的处理
        // head下一个指针指向head
        head.next.next = head;
        // head的下一个指针指向null
        head.next = null;
        // 最后返回最后一个节点p
        return p;
    }
}
这篇关于链表类(Linked List)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!