您现在的位置是：首页 >技术杂谈 >数据结构-链表及相关算法网站首页技术杂谈

数据结构-链表及相关算法

echo洋阳 2023-06-01 04:00:02
简介数据结构-链表及相关算法 
// 单链表节点的结构
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

链表

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含data 域，next域:指向下一个节点.
  3. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定.

基础知识

哈希表的简单介绍

  1. 哈希表在使用层面上可以理解为一种集合结构
  2. 如果只有key，没有伴随数据value，可以使用HashSet结构(C++中叫UnOrderedSet)
  3. 如果既有key，又有伴随数据value，可以使用HashMap结构(C++中叫UnOrderedMap)
  4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
  5. 使用哈希表增(put)、删(remove)、改(put)和查(get)的操作，可以认为时间复杂度为
    O(1)，但是常数时间比较大
  6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地
    址的大小

在java中 HashSet就是一个只使用HashMap的key的一个集合。

有序表的简单介绍

  1. 有序表在使用层面上可以理解为一种集合结构
  2. 如果只有key，没有伴随数据value，可以使用TreeSet结构(C++中叫OrderedSet)
  3. 如果既有key，又有伴随数据value，可以使用TreeMap结构(C++中叫OrderedMap)
  4. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事
  5. 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织
  6. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现
    不同
  7. 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
  8. 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占
    用是这个东西内存地址的大小
  9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复
    杂度

有序表的固定操作：

  1. void put(K key, V value)：将一个（key，value）记录加入到表中，或者将key的记录
    更新成value。
  2. V get(K key)：根据给定的key，查询value并返回。
  3. void remove(K key)：移除key的记录。
  4. boolean containsKey(K key)：询问是否有关于key的记录。
  5. K firstKey()：返回所有键值的排序结果中，最左（最小）的那个。
  6. K lastKey()：返回所有键值的排序结果中，最右（最大）的那个。
  7. K floorKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，
    key的前一个。
  8. K ceilingKey(K key)：如果表中存入过key，返回key；否则返回所有键值的排序结果中，key的后一个。
    以上所有操作时间复杂度都是O(logN)，N为有序表含有的记录数

练习

反转单链表和双链表

节点结构：

public class TreeNode {
	public int num;
	public TreeNode next;
	public TreeNode last;
	public TreeNode(int num) {
		this.num = num;
	}
	public TreeNode() {}
}
public class Node {
	public int num;
	public Node next;
	public Node(int num, Node next) {
		this.num = num;
		this.next = next;
	}
}

两种方式反转链表结构：

/**
	 * 反转单向链表
	 * while循环
	 */
	public static Node reversal1(Node head) {
		Node last = head.next;
		head.next = null;
		while (last != null) {
			Node temp = last.next;
			last.next = head;
			head = last;
			last = temp;
		}
		return head;
	}

	/**
	 * 反转单链表
	 * 递归
	 * @param head
	 * @return
	 */
	public static Node reversal2(Node head) {
		if(head.next == null) {
			return head;
		}
		Node last = reversal2(head.next);
		head.next.next = head;
		head.next = null;
		return last;
	}


	/**
	 * 反转双向链表
	 * 循环
	 * @param head
	 * @return
	 */
	public static TreeNode reversal3(TreeNode head) {
		TreeNode next = head.next;
		head.next = null;
		while (next != null) {
			head.last = next;
			TreeNode temp = next.next;
			next.next = head;
			head = next;
			next = temp;
		}
		return head;
	}
	/**
	 * 反转双向链表
	 * 递归
	 * @param head
	 * @return
	 */
	public static TreeNode reversal4(TreeNode head) {
		if (head.next == null) {
			return head;
		}
		TreeNode node = reversal4(head.next);
		head.next.last = head.next.next;
		head.next.next = head;
		head.next = null;
		return node;
	}

打印两个有序链表的公共部分

public static void portion(Node n1, Node n2) {
		while(n1 != null && n2 != null) {
			if (n1.num == n2.num) {
				System.out.print(n1.num);
				n1 = n1.next;
				n2 = n2.next;
			}else if (n1.num < n2.num) {
				n1 = n1.next;
			}else if (n1.num > n2.num) {
				n2 = n2.next;
			}
		}
	}

技巧

面试时链表解题的方法论

  1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
  2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

重要技巧：

  1. 额外数据结构记录（哈希表等）
  2. 快慢指针

示例

判断回文链表

/**
	 * 不使用额外的空间，适用于面试
	 * @param head
	 * @return
	 */
	public static boolean plalindrome2(Node head) {
		//首先通过快慢指针找到中间的节点，如果是偶数：中间左边，奇数：中间节点
		Node slowNode = head;
		Node quickNode  = head;
		while(quickNode.next!= null && quickNode.next.next != null) {
			slowNode = slowNode.next;
			quickNode = quickNode.next.next;
		}
		//此时慢指针，就到了中间位置，那么在此后面的的节点 指针反转
		quickNode = slowNode.next;
		slowNode.next = null;
		while (quickNode != null) {
			Node temp = quickNode.next;
			quickNode.next = slowNode;
			slowNode = quickNode;
			quickNode = temp;
		}
		while (head.next != null && slowNode.next != null) {
			if (head.num != slowNode.num) {
				return false;
			}
			head = head.next;
			slowNode = slowNode.next;
		}
		return true;
	}


	/**
	 * 使用额外的数据结构，空间复杂度高，适用于笔试
	 * @param head
	 * @return
	 */
	public static boolean plalindrome1(Node head) {
		Stack<Node> stack = new Stack();
		Node node = head;
		while (node != null) {
			stack.add(node);
			node =	node.next;
		}
		while (head != null) {
			if (head.num != stack.pop().num) {
				return false;
			}
			head = head.next;
		}
		return true;
	}

将单向链表按某值划分成左边小、中间相等、右边大的形式

【题目】给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。

/**
	 * 使用有限的变量解答题目
	 * @param node
	 * @param num
	 * @return
	 */
	private static Node pivot1(Node node, int num) {
		Node ssNode = null;
		Node seNode = null;

		Node msNode = null;
		Node meNode = null;

		Node bsNode = null;
		Node beNode = null;

		while (node != null) {
			if (node.num < num) {
				if (ssNode != null) {
					seNode.next = node;
					seNode = node;
				}else {
					ssNode = node;
					seNode = node;
				}
			}else if (node.num > num) {
				if (bsNode != null) {
					beNode.next = node;
					beNode = node;
				}else {
					bsNode =node;
					beNode = node;
				}
			}else if (node.num == num){
				if (msNode != null) {
					meNode.next = node;
					meNode = node;
				}else {
					msNode = node;
					meNode = node;
				}
			}
			node = node.next;
		}

		if (ssNode == null) {
			if (meNode == null) {
				ssNode = bsNode;
			}else {
				meNode.next= bsNode;
				ssNode = msNode;
			}
		}else {
			if (meNode == null) {
				seNode.next = bsNode;
			}else {
				seNode.next = msNode;
				meNode.next = bsNode;
			}
		}
		return ssNode;
	}

	/**
	 * 采用数组 的结构 然后利用快速排序的思路，进行处理
	 * @param node
	 * @param num
	 */
	private static void pivot(Node node, int num) {
		Node[] nodes = new Node[6];
		int i = 0;
		while (node != null) {
			nodes[i++] = node;
			node = node.next;
		}
		System.out.println(Arrays.toString(nodes));
		int start = 0, end = nodes.length-1;
		for (int j = 0; j <= end; j++) {
			if (nodes[j].num < num) {
				Node temp = nodes[j];
				nodes[j] = nodes[start];
				nodes[start] = temp;
				start++;
			}else if (nodes[j].num > num) {
				Node temp = nodes[j];
				nodes[j] = nodes[end];
				nodes[end] = temp;
				j--;
				end --;
			}
		}
		System.out.println(Arrays.toString(nodes));
	}

复制含有随机指针节点的链表

【题目】一种特殊的单链表节点类描述如下

class Node {
int value;
Node next;
Node rand;
Node(int val) {
value = val;
}
}

rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节
点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点
head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
【要求】时间复杂度O(N)，额外空间复杂度O(1)

/**
	 * 使用 Map数据结构 
	 * @param head
	 * @return
	 */
	public static ListNode copy(ListNode head) {
		Map<ListNode, ListNode> map = new HashMap<>();
		ListNode node = head;

		while (node != null) {
			map.put(node, new ListNode(node.value));
			node = node.next;
		}
		ListNode hListNode = head;
		while (head != null) {
			map.get(head).next = map.get(head.next);
			map.get(head).rand = map.get(head.rand);
			head = head.next;
		}
		return map.get(hListNode);
	}


	/**
	 *  不使用额外空间 
	 * @param head
	 * @return
	 */
	public static ListNode copy1(ListNode head) {
		ListNode node = head;
		ListNode temp;
		while (node != null) {
			temp = node.next;
			node.next = new ListNode(node.value);
			node.next.next = temp;
			node = temp;
		}

		node = head;
		while (node != null) {
			temp = node.next;
			if (node.rand == null) {
				temp.rand = null;
			}else {
				temp.rand = node.rand.next;
			}
			node = node.next.next;
		}
		return head.next;
	}

两个单链表相交的一系列问题

【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实
现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返
回null
【要求】如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度
请达到O(1)。

//没做

题

递归反转单链表

public ListNode reverse(ListNode head) {
		if (head.next == null) {
			return head;
		}
		ListNode lastListNode = reverse(head.next);
		head.next.next = head;
		head.next = null;
		return lastListNode;
	}

递归反转前n个节点

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
public ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

递归反转指定范围的节点

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。

https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-shua-lian-biao-ti-mu-xun-lian-di-gui-si-wei/di-gui-fan-zhuan-lian-biao-de-yi-bu-fen

leetcode

/**
 * 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 success1 = null;
	public ListNode reverseBetween(ListNode head, int left, int right) {
		if (left == 1) {
			return reverseBetween(head, right);
		}
		head.next = reverseBetween(head.next, --left, --right);
		return head;
    }

	public ListNode reverseBetween(ListNode head, int n) {
		if (n == 1) {
			success1 = head.next;
			return head;
		}
		ListNode laListNode = reverseBetween(head.next, --n);
		head.next.next = head;
		head.next = success1;
		return laListNode;
    }

}

k个一组反转链表

我的代码：

/**
 * 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 reverseKGroup(ListNode head, int k) {
		 ListNode[] arr = reverse(head, k);
		 ListNode preListNode = arr[2];
		 ListNode preListNode1 = arr[0];
		 while (arr[1] != null) {
			 if (!judge(arr[1], k)) {
				break;
			}
			arr = reverse(arr[1], k);
			preListNode.next = arr[0];
			preListNode = arr[2];
		}
		 return preListNode1;
	 }
	 public boolean judge(ListNode head, int k) {
		 ListNode node = head;	 
		 while (node != null) {
			node = node.next;
			k--;
			if (k == 0) {
				return true;
			}
		}
		 return false;
	 }
	 
	 public ListNode[] reverse(ListNode head, int k) {
		 ListNode[] arr = new ListNode[3];
		 ListNode preNode = head;
		 ListNode currentNode = head.next;
		 ListNode tempListNode = null;
		 while (currentNode != null&&k>1) {
			tempListNode = currentNode.next;
			currentNode.next = preNode;
			preNode = currentNode;
			currentNode = tempListNode;
			if (k == 2) {
				break;
			}
			--k;
		}
		head.next = currentNode;
		arr[0] = preNode;
		arr[1] = currentNode;
		arr[2] = head;
		return arr;
	 }

}

拉布拉多

/**
 * 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 reverseKGroup(ListNode head, int k) {
		 if (head == null) {
			return null;
		}
		 ListNode a,b;
		 a = head;
		 b = head;
		 for (int i = 0; i < k; i++) {
			 if (b == null) {
				return head;
			}
			b = b.next;
		}
		// 反转前 k 个元素
	    ListNode newHead = reverse(a, b);
	    // 递归反转后续链表并连接起来
	    a.next = reverseKGroup(b, k);

		return newHead; 
	 }
	public ListNode reverse(ListNode a, ListNode b) {
		ListNode pre,cur,temp;
		pre = a;
		cur = a.next;
		while (cur != b) {
			temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		return pre;
	}

}

回文链表

方式一：

空间复杂度为O(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 boolean isPalindrome(ListNode head) {
        ListNode a = head;
		ListNode b = head;
		while (b.next != null && b.next.next != null) {
			b = b.next.next;
			a = a.next;
		}
		ListNode c;
		c = a.next;
		a.next = null;
		while (c != null) {
			b = c.next;
			c.next = a;
			a = c;
			c = b;
		}
		c = a;
		b = head;
		while (b != null && a != null) {
			if (b.val != a.val) {
				return false;
			}
			b = b.next;
			a = a.next;
		}
		//复原
  
		return true;
    }
}

方式二：

使用栈

/**
 * 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 boolean isPalindrome(ListNode head) {
         Stack<Integer> stack = new Stack<>();
		ListNode node  = head;
		while (node != null) {
			stack.add(node.val);
			node = node.next;
		}
		while (head != null) {
			if (stack.pop() != head.val) {
				return false;
			}
			head = head.next;
		}
		return true;
    }
}

方式三：

使用递归

/**
 * 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 {
   ListNode left;
	public boolean isPalindrome(ListNode head) {
		left = head;
		return traverse(head);
   }

	public boolean traverse(ListNode head) {
	    // 前序遍历代码
	    if (head == null) {
			return true;
		}
	  
	    // 后序遍历代码
	    boolean res =  traverse(head.next);
	    boolean b = res && head.val == left.val;
	    left = left.next;
	    return b;
	}
}

面试题 02.02. 返回倒数第 k 个节点

//双指针
public int kthToLast(ListNode head, int k) {
       ListNode n1 = head;
		ListNode n2 = head;

		while (k != 0) {
			n1 = n1.next;
			k--;
		}
		while (n1 != null) {
			n1 = n1.next;
			n2 = n2.next;
		}

		return n2.val;
    }

彩蛋

加入我的知识星球，加入自学编程者的聚集地。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐