技巧一：理解指针或引用的含义
技巧二：警惕指针丢失和内存泄漏
技巧三：利用哨兵简化实现难度
技巧四：重点留意边界条件处理
技巧五：举例画图，辅助思考
技巧六：多写多练，没有捷径
练习题目：
1、单链表反转链
单链表反转(简单)力扣链接
// 迭代方式class Solution {public ListNode reverseList(ListNode head) {// 当只有一个节点和空节点的时候，直接将头节点进行返回if(head == null || head.next == null) return head;// node表示的是当前指针所在位置ListNode current = head.next;// b表示前一个指针ListNode previous = head;// 将头指针的下一个节点指向空，因为不这样处理的话，反转后的链表会在最后两个节点中形成闭环。// 错误如下: Error - Found cycle in the ListNodehead.next = null;// 下一个节点ListNode behind;while(current != null) {behind = current.next;// 交换节点current.next = previous;previous = current;current = behind;}return previous;}}// 递归方式/**每次递归都会得到的数据有head表示的是当前的节点可以有：head head.next需要做的是将head.next.next = head;从最后面开始做起*/class Solution {0public ListNode reverseList(ListNode head) {return recursiveListNode(head);}// 使用递归方式public ListNode recursiveListNode(ListNode head) {if(head == null || head.next == null) {//这里有两种情况。一种是只有一个节点，或者是已到达了组后一个节点return head;}// 这个是得到递归的最后一个节点。也就是反转后的头节点ListNode last = recursiveListNode(head.next);// head表示的是cur节点，找到他的前一个节点（反转后的前一个节点）ListNode cur = head;// 这里的pre节点表示的是反转后的链表的尾节点ListNode pre = last;while(pre.next != null) {pre = pre.next;}// pre反转后的尾节点, cur需要当前方法中加入的尾节点。进行cur连接到尾部pre.next = cur;cur.next = null;return last;}}
单链表反转(中等)力扣链接
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;for (int i = 0; i < left - 1; i++) {pre = pre.next;}ListNode rightNode = pre;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode.next;}ListNode leftNode = pre.next;ListNode curr = rightNode.next;pre.next = null;rightNode.next = null;reverseLinkedList(leftNode);pre.next = rightNode;leftNode.next = curr;return dummyNode.next;}private void reverseLinkedList(ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}}}
2、表中环的检测
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/public class Solution {// ListNode表示的是链表为环的位置的节点public ListNode detectCycle(ListNode head) {// if(head == null || head.next == null) return null;// return getCycleNode(head);return fastAndSlow(head);}//public ListNode fastAndSlow(ListNode node) {ListNode slow = node;ListNode fast = node;// 这里说明的是快指针还能继续往下走，那么满指针也能往下走while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(fast==null) return null;if(fast == slow) { // 说明存在着环// 说明 n 表示的是头节点到环入口的位置， h是环有多少个节点，*表示任意个// slow走的步数为 n + x// fast走的步数为 *h + n+x// 存在着 2n + 2x = *h + n+x//===》 n+x = *h//===》 n = *h - x, ===> 这里有个意思就是节点到环入口的位置，快或者满指针加上就又有一个环也就是又到了入口的位置。ListNode pre = node;ListNode fast1 = fast;while(pre != fast1) {pre = pre.next;fast1 = fast1.next;}return pre;}}return null;}// 使用set保存每一个ListNode,存在的话就进行返回重复的static Set<ListNode> set = new HashSet<ListNode>();public ListNode getCycleNode(ListNode head) {while(head != null) {if(set.contains(head)) {return head;}set.add(head);head = head.next;}return null;}}
3、两个有序的链表合并
// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* 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 mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode(-1); //
if(list1 == null && list2 == null) return head.next;
ListNode first = head;
while(list1 != null || list2 != null) {
if(list1 == null) {// 第一个链表为空，第二个表直接添加进去
while(list2 != null) {
head.next = list2;
list2 = list2.next;
head = head.next;
}
return first.next;
}
if(list2 == null) {
while(list1 != null) {
head.next = list1;
list1 = list1.next;
head = head.next;
}
return first.next;
}
if(list1.val < list2.val) {
head.next = list1;
list1 = list1.next;
head = head.next;
} else {
head.next = list2;
list2 = list2.next;
head = head.next;
}
}
return first.next;
}
}
// 递归方式
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
return getHead(list1, list2);
}
// 递归找到最后一个节点，将最后两个节点进行比较s形
public static ListNode getHead(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
if(l1.val < l2.val) {
l1.next = getHead(l1.next, l2);
return l1;
} else {
l2.next = getHead(l1, l2.next);
return l2;
}
}
}
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-in-between-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode node = list1;
ListNode first = null;
for(int i = 0; i < a; i++) { //取到拼接的开始的节点
first = list1;
list1 = list1.next;
}
ListNode last = null;
list1 = node;
for(int j = 0; j< b+2; j++) {//取到拼接的结束的节点的后一个节点
last = list1;
list1 = list1.next;
}
first.next = list2;
while(list2.next!=null) {
list2 = list2.next;
}
list2.next = last;
return node;
}
}
23. 合并K个升序链表
下面是迭代合并，那如果是合并合并或者使用优先队列(PriorityQueue)呢？（优先队列(PriorityQueue)？？什么是优先队列）
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//ListNode node = new ListNode(Integer.MIN_VALUE);
ListNode node = null;
ListNode result = node;
for(int i = 0; i<lists.length; i++) { // 迭代合并
if(lists[i] == null) continue;
node = getHead(node, lists[i]);
}
return node;
}
public static ListNode getHead(ListNode l1, ListNode l2) { // 合并两个链表
ListNode head = new ListNode();
ListNode head1 = head;
while(l1!=null || l2!=null) {
if(l1==null || l2==null) {
head.next = (l1==null)?l2:l1;
return head1.next;
}
if(l1.val < l2.val) {
head.next = l1;
head = head.next;
l1 = l1.next;
} else {
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
return null;
}
}
4、删除链表倒数第 n 个结点
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// return iterationLink1(head, n);
// return iterationLink2(head, n);
ListNode dummyNode = new ListNode();
dummyNode.next = head;
int a = recursiveDelete(dummyNode, n+1);
System.out.println(a);
return dummyNode.next;
}
// 递归
public static int recursiveDelete(ListNode node, int n) {
if(node == null) {// 返回
return 0;
}
int count = recursiveDelete(node.next, n)+1;
if(count == n) {
// System.out.println("删除" + node.val + " " + count);
if(node.next!=null) {
node.next = node.next.next;
}
}
return count;
}
// 迭代2 先走n步，然后在通过一个节点从头开始走，直到第一个节点走到末尾
public static ListNode iterationLink2(ListNode head, int n) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode first = dummyNode;
ListNode last = dummyNode;
while((n--) >= 0) { // 走n+1步，因为要找到删除节点的前一个节点 // for(int i = 0; i <= n; i++) {
first = first.next;
}
while(first!=null) {
first = first.next;
last = last.next;
}
last.next = last.next.next;
return dummyNode.next;
}
// 迭代1
public static ListNode iterationLink1(ListNode head, int n) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode ans = dummyNode;
int count = 0;
while(head!=null) {
count++;
head = head.next;
}
System.out.println(count);
for(int i = 0; i < (count - n); i++) {
dummyNode = dummyNode.next;
}
if(dummyNode.next != null) {
dummyNode.next = dummyNode.next.next;
}
return ans.next;
}
}
5、求链表的中间结点
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
若有收获，就点个赞吧
0 人点赞
