2.1 线性表

什么是线性表

? 线性表是 n 个数据元素的有限序列,最常用的是链式表达,通常也叫作线性链表或者链表。在链表中存储的数据元素也叫作结点,一个结点存储的就是一条数据记录。每个结点的结构包括两个部分:

  • 第一是具体的数据值

  • 第二是指向下一个结点的指针

    这是一个单项链表

技术图片

如果最后一个指向第一个就会形成一个循环链表

?技术图片

增加一个指向上一个结点的指针,这样就得到了双向链表

技术图片

双向链表循环链表进行融合,就得到了双向循环链表

技术图片

案例

例 1, 链表的翻转

? 给定一个链表,输出翻转后的链表。例如,输入1 ->2 -> 3 -> 4 ->5,输出 5 -> 4 -> 3 -> 2 -> 1。

核心代码如下

		// 前一个节点
		Node<Integer> preNode = null;
		Node<Integer> curNode = head;
		Node<Integer> nextNode = null;

		while (curNode != null) {
			//重点	
			nextNode = curNode.getNext();// next 指向当前下一个节点
			curNode.setNext(preNode);// 将当前节点的next指向前一个节点
			preNode = curNode;// preNode 指针向后移动
			curNode = nextNode; // curNode指针向后移动
		}

		return preNode;

流程如下图

技术图片

全部代码

public class SingleLinkedReverse {

	public static void main(String[] args) {
		// 初始化一个链表
		Node<Integer> head = new Node<Integer>(1, new Node<Integer>(2,
				new Node<Integer>(3, new Node<Integer>(4, new Node<Integer>(5,null)))));

		Node<Integer> newNode = reverseLinkedNode(head);

		while (newNode != null) {
			System.out.print(newNode.getData() + "-->");
			newNode = newNode.next;
		}
	}

	public static Node<Integer> reverseLinkedNode(Node<Integer> head) {
		if (head == null || head.next == null) {
			return head;
		}

		// 前一个节点
		Node<Integer> preNode = null;
		Node<Integer> curNode = head;
		Node<Integer> nextNode = null;

		while (curNode != null) {
			//重点	
			nextNode = curNode.getNext();// next 指向当前下一个节点
			curNode.setNext(preNode);// 将当前节点的next指向前一个节点
			preNode = curNode;// preNode 指针向后移动
			curNode = nextNode; // curNode指针向后移动
		}

		return preNode;
	}

	static class Node<T> {
		T data;
		Node<T> next;

		public Node() {
		}

		public Node(T data, Node<T> next) {
			super();
			this.data = data;
			this.next = next;
		}

		public T getData() {
			return data;
		}

		public void setData(T data) {
			this.data = data;
		}

		public Node<T> getNext() {
			return next;
		}

		public void setNext(Node<T> next) {
			this.next = next;
		}

	}

}

例 2,快慢指针

? 给定一个奇数个元素的链表,查找出这个链表中间位置的结点的数值。

? 核心:利用快慢指针进行处理。其中快指针每次循环向后跳转两次,而慢指针每次向后跳转一次,循环结束慢指针指向的就是中间节点

while(fast && fast.next && fast.next.next){

    fast = fast.next.next;

    slow = slow.next;
}

例 3,有环的链表--如何判断一个链表是否有环

技术图片

核心:假设链表有环,这个环里面就像是一个跑步赛道的操场一样。经过多次循环之后,快指针和慢指针都会进入到这个赛道中,就好像两个跑步选手在比赛。快指针每次走两格,而慢指针每次走一格,相对而言,快指针每次循环会多走一步。这就意味着:

  • 如果链表存在环,快指针和慢指针一定会在环内相遇,即 fast == slow 的情况一定会发生。
  • 反之,则最终会完成循环,二者从未相遇。

2.1 线性表

原文地址:https://www.cnblogs.com/tomarsNi/p/13862606.html