大佬教程收集整理的这篇文章主要介绍了LeetCode入门指南 之 链表，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
存在一个按升序排列的链表，给你这个链表的头节点
head，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
//删除重复元素但保留一个的情况下头结点不可能被删除，故不需要哑结点
ListNode cur = head;
/**
* 拿当前结点和当前结点后继结点比较,
* 若后继结点与当前结点值相同则删除后继结点,
* 否则cur后移，直到 cur.next 为 null
*/
while (cur.next != null) {
if (cur.next.val == cur.val) {
//删除后继结点后无需后移，否则会漏过连续重复结点（3个及以上重复结点的情况）
cur.next = cur.next.next;
} else {
cur = cur.next;
}
return head;
}
}
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
//删除所有重复元素，当头结点为重复元素时要删除头结点，所以需要哑结点
ListNode dummy = new ListNode(-1);
//哑结点指向头结点
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
//发现重复元素
if (cur.next.val == cur.next.next.val) {
//重复值
int tempVal = cur.next.val;
ListNode temp = cur.next.next;
//找到最后一个重复元素
while(temp.next != null && temp.next.val == tempVal) {
temp = temp.next;
}
//删除所有重复元素
cur.next = temp.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
反转一个单链表。
思路一：迭代法：
/**
* 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 pre = null;
//当前结点
ListNode cur = head;
while (cur != null) {
//用来保存当前结点的下一个结点
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
思路二：递归（锻炼递归思维）：
首先给出函数定义，如此题：ListNode reverseList(ListNode head)
head为头结点的链表不要用脑袋去模拟递归栈，根据函数的定义去处理递归的子问题，要具体到一个结点要做的事情
确定base case
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
//base case, 当链表只有一个结点时退出递归
if (head.next == null) {
return head;
}
/**
* 具体到头结点来说，反转当前链表只需要两步：
* 1.反转以head.next为头的链表
* 2.将head插入head.next为头的链表反转之后的链表末尾
*/
ListNode vhead = reverseList(head.next); //根据递归函数定义，返回反转之后的链表头
//反转之后head.next位于链表尾部，将head插入head.next之后
head.next.next = head;
head.next = null;
return vhead;
}
}
反转从位置 @H_909_76@m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ @H_909_76@m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
class Solution {
public ListNode reversebetween(ListNode head, int left, int right) {
if (head == null) {
return head;
}
//可能从第一个结点开始反转，故需要哑结点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
//找到left之前和right之后的结点以便反转后拼接
ListNode l = dummyNode, r = dummyNode;
for (int i = 0; i < left - 1; i++) { //l为left的前一个结点
l = l.next;
}
for (int i = 0; i < right + 1; i++) { //r为right后一个结点
r = r.next;
}
ListNode last = reverse(l.next, r);
l.next.next = r;
l.next = last;
return dummyNode.next;
}
//反转以left开头，right结尾的链表(左闭右开)，返回反转后的链表头结点
private ListNode reverse(ListNode left, ListNode right) {
ListNode pre = null, cur = left, next = left;
while (cur != right) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
当头节点不确定是否会被操作的时候，使用哑巴节点
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
递归解法（锻炼递归思维）：
class Solution {
/** 明确递归函数的定义：
* k个一组反转以head为头结点的链表，并返回反转后的头结点
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return head;
}
/**
* 按照递归函数定义，对第一组结点来说，k个一组反转整个链表分为两步：
* 1.反转第一组结点
* 2.将反转后的第一组结点与反转后的其他组结点拼接
*/
//找到一组共k个结点，l为第1个结点，r为第k个结点的后一个结点,因为reverse的参数为左闭右开
ListNode l = head, r = head;
//移动k次后，r指向第k+1个点
for (int i = 0; i < k; i++) {
//base case, 当结点结点不足k个时，无需反转直接返回
if (r == null) return l;
r = r.next;
}
ListNode newHead = reverse(l, r);
//反转后第一组的头结点变为尾结点
l.next = reverseKGroup(r, k);
return newHead;
}
//翻转left和right之间的结点，左闭右开
private ListNode reverse(ListNode left, ListNode right) {
ListNode pre = null, cur = left;
while (cur != right) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
递归解法（锻炼递归思维）：
class Solution {
/**
* 定义：
* 合并链表l1， l2，返回合并后的链表
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//base case
//若l1或l2为空，说明l1或l2为空链表，直接返回另外一个链表即为合并后的链表
if (l1 == null) return l2;
if (l2 == null) return l1;
/**
* 按照递归函数定义，对当前结点l1， l2来说，合并链表分为两部：
* 1.若l1.val 小于 l2.val，只需将l1.next 和 l2合并之后的链表拼接在l1之后
* 2.反之将l2.next 和 l1 合并之后的链表拼接在l2之后
*/
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
迭代解法：
提示：迭代法根据代码在本子上画一下很容易理解
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(-1);
ListNode pre = dummyNode;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
//l1还有剩余
if (l1 != null) {
pre.next = l1;
} else {
pre.next = l2;
}
return dummyNode.next;
}
}
给你一个链表的头节点
head和一个特定值x，请你对链表进行分隔，使得所有 小于x的节点都出现在 大于或等于x的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
class Solution {
/**
* 审题：将链表中小于目标值的结点全部放置在大于等于目标值的结点之前。
* 显然，可以遍历原来的链表时将链表分为两个链表，一个链表存储所有小于目标值的结点（相对顺序不变），
* 另一个链表存储所有大于等于目标值的结点（相对顺序不变）;
* 最后将大的链表拼接在小的链表之后。
*/
public ListNode partition(ListNode head, int X) {
if (head == null) {
return head;
}
//创建两个哑结点，使用尾插法建立新链表 (头插法会改变相对顺序)
ListNode smallDummy = new ListNode(-1);
ListNode bigDummy = new ListNode(-1);
ListNode smallPre = smallDummy;
ListNode bigPre = bigDummy;
//遍历链表
ListNode cur = head;
while (cur != null) {
if (cur.val < X) {
smallPre.next = cur;
smallPre = smallPre.next;
} else {
bigPre.next = cur;
bigPre = bigPre.next;
}
cur = cur.next;
}
//bigPre.next可能不为null
bigPre.next = null;
//拼接
smallPre.next = bigDummy.next;
return smallDummy.next;
}
}
对链表进行插入排序。
class Solution {
/**
* 插入排序思路：
* 用last指针标识已经有序部分的最后一个结点；
* 遍历剩余无序结点，依次插入有序部分；
* 初始第一个结点为有序结点。
*
*/
public ListNode insertionSortList(ListNode head) {
//没有结点或只有一个结点
if (head == null || head.next == null) {
return head;
}
//方便在头结点之前插入
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode last = head;
ListNode cur = head.next;
while (cur != null) {
//若当前结点大于等于有序部分的最后一个结点则说明本身有序，直接将last后移
if (cur.val >= last.val) {
last = cur;
cur = cur.next;
} else {
//在有序部分中找到插入的位置
ListNode pre = dummy;
while(pre.next.val < cur.val) {
pre = pre.next;
}
//cur插入时会修改next
ListNode next = cur.next;
//插入
cur.next = pre.next;
pre.next = cur;
last.next = next;
cur = next;
}
}
return dummy.next;
}
}
给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。进阶：
- 你可以在
O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
归并排序(空间复杂度为O(nlogn))：
class Solution {
public ListNode sortList(ListNode head) {
//base case 没有或者只有一个结点，退出递归
if (head == null || head.next == null) {
return head;
}
ListNode mid = getMidNode(head);
ListNode rightHead = mid.next;
//切断
mid.next = null;
//分别对左右两个链表进行归并排序
ListNode left = sortList(head);
ListNode right = sortList(rightHead);
//合并后返回
return mergeList(left, right);
}
//使用快慢指针寻找链表中点
private ListNode getMidNode(ListNode head) {
//该初始化方式得到的结果中：
//当结点有偶数个时，slow指向两个中间结点的前一个结点;
//当结点有奇数个时，slow指向中间结点。
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//合并两个有序链表
private ListNode mergeList(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = mergeList(l1.next, l2);
return l1;
} else {
l2.next = mergeList(l1, l2.next);
return l2;
}
}
}
快速排序：
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
return quickSort(head, null);
}
//对head开头，end结尾的链表进行快排(左闭右开)，返回排序后的结点
private ListNode quickSort(ListNode head, ListNode end) {
//base case, 没有结点或只有一个结点默认有序，退出递归
if (head == end || head.next == end) {
return head;
}
ListNode left = head, right = head; //pivot为head
ListNode cur = head.next; //用来遍历剩余结点
while (cur != end) {
if (cur.val <= head.val) { //头插法将小于等于pivot的结点放置在pivot之前
//cur.next 被改变，先保存下来
ListNode next = cur.next;
cur.next = left;
left = cur;
cur = next;
} else { //尾插法将大于pivot的结点放置在pivot之后
right.next = cur;
right = cur;
cur = cur.next;
}
}
right.next = end; //此步很重要
ListNode vhead = quickSort(left, head);
head.next = quickSort(head.next, end);
return vhead;
}
}
给定一个单链表 L：L0 →L1 →…→Ln-1 →Ln ， 将其重新排列后变为： L0 →Ln →L1 →Ln-1 →L2 →Ln-2 →…
class Solution {
/**
* 思路：
* 找到中点，反转后半部分，然后交叉合并为一个链表
*/
public void reorderList(ListNode head) {
//没有或只有1、2个结点无需操作
if (head == null || head.next == null || head.next.next == null) {
return;
}
ListNode midNode = getMidNode(head);
ListNode nextHalf = midNode.next;
midNode.next = null; //切断前后两部分连接
//反转后半部分链表
ListNode nHead = reverse(nextHalf);
//合并链表
Boolean flag = true;
ListNode l1 = head, l2 = nHead;
while (l2 != null) {
if (flag) {
ListNode next = l1.next;
l1.next = l2;
l1 = next;
} else {
ListNode next = l2.next;
l2.next = l1;
l2 = next;
}
flag = !flag;
}
}
private ListNode getMidNode(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。如果链表中存在环，则返回
true。 否则，返回false。
public class Solution {
/**
* 思路：
* 快慢指针，若慢指针最终追上快指针说明有环
*/
public Boolean hasCycle(ListNode head) {
//没有或只有一个结点说明没有环
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回
null。
思路：快慢指针，快慢指针相遇后，慢指针回到头，快慢指针步伐一致一起移动，相遇点即为入环点。有兴趣的可以自己看下官方题解中的推导。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int X) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// 没有结点或只有一个非自环结点
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
//快指针从第一次相交点下一个节点开始移动, 慢指针重新从头开始移动
fast = fast.next; //注意
slow = head;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
// 相遇点即为入环点
return fast;
}
}
return null;
}
}
请判断一个链表是否为回文链表。
思路：快慢指针找到中点，反转后半部分，然后依次比较，最后要记得还原链表
/**
* 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) {
//没有或只有一个结点
if (head == null || head.next == null) {
return true;
}
ListNode mid = getMidNode(head);
ListNode rHead = reverse(mid.next);
//切断
mid.next = null;
ListNode lTemp = head;
ListNode rTemp = rHead;
//右半部分链表长度小于等于左半部分链表长度
while (rTemp != null) {
if (lTemp.val != rTemp.val) {
return false;
}
lTemp = lTemp.next;
rTemp = rTemp.next;
}
//还原
mid.next = reverse(rHead);
return true;
}
//对于偶数个结点和奇数个结点，slow都位于右部分的前一个结点
private ListNode getMidNode(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//反转链表
private ListNode reverse(ListNode head) {
ListNode pre = null, cur = head, next = head;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
slow = head;fast = head.next;的方式使用快慢指针slow指向中点；结点个数为偶数，slow指向左边中点给你一个长度为
n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
//第一次遍历：先复制所有结点，占时不管指针域,并将新旧结点通过HashMap关联起来
Node cur = head;
Map<Node, Node> map = new HashMap<>();
while (cur != null) {
Node newNode = new Node(cur.val);
map.put(cur, newNodE);
cur = cur.next;
}
//第二次遍历：通过HashMap关联各个新结点
cur = head;
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
以上题目整理来自：算法入门（go语言实现），这里给出java实现，实现思想有所不同。
以上是大佬教程为你收集整理的LeetCode入门指南 之 链表全部内容，希望文章能够帮你解决LeetCode入门指南 之 链表所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。