通知
此博客运行在jpress系统上，如果你喜欢此博客模板，请加QQ群：1061691290（whimurmur模板/jpress插件），免费下载使用

leetcode探索之链表学习 单链表

3544人浏览 / 0人评论 | 作者：whisper  | 分类： 设计模式与算法  | 标签： 设计模式与算法  /  leetcode  | 

作者：whisper

链接：http://proprogrammar.com:443/article/245

声明：请尊重原作者的劳动，如需转载请注明出处

    正如我们在概览中提到的那样，链表是一种线性数据结构，它通过引用字段将所有分离的元素链接在一起。有两种常用的链表：单链表和双链表。

    本章节中，我们将从单链表开始，并帮助您：

  • 了解单链表的结构；
  • 在单链表中执行遍历，插入和删除操作；
  • 分析单链表中不同操作的时间复杂度。

    简介 - 单链表

    正如我们在概览中提到的那样，链表是一种线性数据结构，它通过引用字段将所有分离的元素链接在一起。有两种常用的链表：单链表和双链表。

    本章节中，我们将从单链表开始，并帮助您：

  • 了解单链表的结构；
  • 在单链表中执行遍历，插入和删除操作；
  • 分析单链表中不同操作的时间复杂度。

     单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

    下面是一个单链表的例子：

    蓝色箭头显示单个链接列表中的结点是如何组合在一起的。

    结点结构

    以下是单链表中结点的典型定义：

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

    在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。

    操作

    与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

    例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。

    你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中，我们将介绍插入和删除操作，你将了解到链表的好处。

    之后，我们将为你提供练习设计自己的单链表。

    添加操作 - 单链表

    如果我们想在给定的结点 prev 之后添加新值，我们应该：

  1. 使用给定值初始化新结点 cur；
  2. 将 cur 的“next”字段链接到 prev 的下一个结点 next；
  3. 将 prev 中的“next”字段链接到 cur 。

    与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。

    示例

    让我们在第二个结点 6 之后插入一个新的值 9。

    我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15。最后，将结点 6 链接到结点 9。

    插入之后，我们的链表将如下所示：

    在开头添加结点

    众所周知，我们使用头结点来代表整个列表。

    因此，在列表开头添加新节点时更新头结点 head 至关重要。

  1. 初始化一个新结点 cur；
  2. 将新结点链接到我们的原始头结点 head。
  3. 将 cur 指定为 head。

    例如，让我们在列表的开头添加一个新结点 9。

  1. 我们初始化一个新结点 9 并将其链接到当前头结点 23。
  2. 指定结点 9 为新的头结点。 

如何在列表的末尾添加新的结点？我们还能使用类似的策略吗？

    删除操作 - 单链表

    如果我们想从单链表中删除现有结点 cur，可以分两步完成：

  1. 找到 cur 的上一个结点 prev 及其下一个结点 next；
  2. 接下来链接 prev 到 cur 的下一个节点 next。

    在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。

    空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

    示例

    让我们尝试把结点 6从上面的单链表中删除。

    1. 从头遍历链表，直到我们找到前一个结点 prev，即结点 23

    2. 将 prev（结点 23）与 next（结点 15）链接

    结点 6 现在不在我们的单链表中。

    删除第一个结点

    如果我们想删除第一个结点，策略会有所不同。

    正如之前所提到的，我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。

    如果想要删除第一个结点，我们可以简单地将下一个结点分配给 head。也就是说，删除之后我们的头将会是结点 6。

    链表从头结点开始，因此结点 23 不再在我们的链表中。

删除最后一个结点呢？我们还能使用类似的策略吗？

    算法说明

    设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

  • 所有val值都在 [1, 1000] 之内。
  • 操作次数将在  [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。
class MyLinkedList {
    ListNode head;
    int len;
    
    /** Initialize your data structure here. */
    public MyLinkedList() {
        len = 0;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index >= len || index < 0){
            return -1;
        }
        
        ListNode temp = head;
        for(int i = 1; i <= index; i++){
            temp = temp.next;
        }
        
        return temp.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        ListNode temp = new ListNode(val);
        
        if(head == null){
            head = temp;
        }else{
            temp.next = head;
            head = temp;
        }
        
        len++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if(null == head){
            head = new ListNode(val);
        }else{
            ListNode temp = head;
            for(int i = 1; i < len; i++){
                temp = temp.next;
            }
            
            temp.next = new ListNode(val);
        }
        
        len++;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index <= 0){
            addAtHead(val);
        }else if(index < len){
            ListNode temp = head;
            
            for(int i = 1; i < index; i++){
                temp = temp.next;
            }
            
            ListNode newNode = new ListNode(val);
            newNode.next = temp.next;
            temp.next = newNode;
            
            len++;
            
        }else if(index == len){
            addAtTail(val);
        }
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index < len && index >= 0){
            ListNode temp = head;
            
            if(index == 0) {
            	head = head.next;
            }else {
	            for(int i = 1; i < index; i++){
	                temp = temp.next;
	            }
	            
	            temp.next = temp.next.next;
            }
            
            len--;
        }
    }
    
    private class ListNode{
        int val;
        ListNode next;
        
        public ListNode(int val){
            this.val = val;
        }
    }
}

    算法中定义了一个len，方便判断链表长度，一个head头指针作为链表的入口，再看一下其它人的写法

/**
 * A singly linked list with a left sentinel node.
 */
class MyLinkedList {

	/** A very simple node class. */
	private static class Node {
		int val;
		Node next;
	}

	// Predecessor of the first element
	private Node headPred;
	// Predecessor of the tail
	private Node tailPred;
	private int length;

	/** Initialize your data structure here. */
	public MyLinkedList() {
		headPred = new Node();
		tailPred = headPred;
		length = 0;
	}

	/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
	public int get(int index) {
		if ((index < 0) || (index >= length)) {
			return -1;
		}
		return findPred(index).next.val;
	}

	/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
	public void addAtHead(int val) {
		if (length == 0) {
			addAtTail(val);
		} else {
			addAfter(headPred, val);
		}
	}

	/** Append a node of value val to the last element of the linked list. */
	public void addAtTail(int val) {
		addAfter(tailPred, val);
		tailPred = tailPred.next;
	}

	/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
	public void addAtIndex(int index, int val) {
		if (index < 0) {
			addAtHead(val);
		} else if (index == length) {
			addAtTail(val);
		} else if ((index >= 0) && (index < length)) {
			addAfter(findPred(index), val);
		}
	}

	/** Delete the index-th node in the linked list, if the index is valid. */
	public void deleteAtIndex(int index) {
		if ((index >= 0) && (index < length)) {
			Node pred = findPred(index);
			if (index == length - 1) { // Remove last element
				// Move tail to the left
				tailPred = pred;
			}
			pred.next = pred.next.next;
			--length;
		}
	}

	/** Return the predecessor of the index-th node. */
	private Node findPred(int index) {
		Node pred = headPred;
		for (int i = 0; i < index; ++i) {
			pred = pred.next;
		}
		return pred;
	}

	/** Add an element after the given node. */
	private void addAfter(Node pred, int val) {
		Node node = new Node();
		node.val = val;
		node.next = pred.next;
		pred.next = node;
		++length;
	}
}

    这里定义了头指针、尾指针和长度，并定义了findPred来找到索引节点的前一个节点，addAfter在节点后增加一个节点，通过在其它方法中调用这两个方法来完成相关操作，效率还是不错的。

亲爱的读者：有时间可以点赞评论一下

我慒慒懂懂过了一年，这一年似乎没有改变，守着一个人的世界，空空如也
点赞(0) 打赏

相关文章

LeetCode 312. Burst Balloons（戳气球）
LeetCode 312. Burst Balloons（戳气球）
有向无环带权图的最短路径及长度
有向无环带权图的最短路径及长度
拓扑排序获取所有可能序列JAVA实现
拓扑排序获取所有可能序列JAVA实现

作者其它文章

数据结构 绪论
数据结构 绪论
数据结构第一章 线性表
数据结构第一章 线性表
考研数学导学
考研数学导学

全部评论

还没有评论！