算法记录——链表

2.链表

2.1判断是否是回文链表

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) {Stack<ListNode> listNodes = new Stack<>();ListNode p = head;//利用栈反转链表，判断是否是回文链表while (p != null) {//将链表中所有元素入栈listNodes.push(p);p = p.next;}while (!listNodes.empty()) {if (listNodes.pop().val == head.val) {//head = head.next;} else {return false;}}return true;}
}

2.方法2：利用快慢指针

/*** 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 fast = head;//代表慢指针，一次走一步ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}//退出循环时，如果链表节点是奇数个，快指针在尾节点，慢指针在中点。如果是偶数个，快指针还是在尾节点，慢指针在中点前一个。//把右半部分链表反转slow = reverseList(slow.next);while (slow != null) {if (head.val != slow.val) return false;//值不相同，直接返回falsehead = head.next;slow = slow.next;}return true;}//反转链表public static ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;while (cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

2.2 模板题：反转链表

/*** 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) {//cur：用于遍历链表元素的指针，代表当前遍历到的节点，初始化当然为head了ListNode cur = head;//pre：代表当前cur节点，反转后应该指向的节点。因为cur初始在head，反转以后就是尾节点了指向null，所以pre初始化为nullListNode pre = null;while(cur != null){//当元素还没遍历完的时候//在cur指向pre前，用于保存cur.next，防止链表找不到了。ListNode temp = cur.next;//让当前节点cur，指向precur.next = pre;//让pre变为反转链表的最前面一个节点pre = cur;//让cur移动到原链表的头节点cur = temp;}// 注意：pre的含义还是反转链表的头节点！return pre;}
}

复杂度分析：
时间复杂度 O(N)O(N)O(N) ： 遍历链表使用线性大小时间。
空间复杂度 O(1)O(1)O(1) ： 变量 pre 和 cur 使用常数大小额外空间。

已经是最优的解法了，还有一种递归方法就不赘述了。

2.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 partition(ListNode head, int x) {
if (head == null || head.next == null) return head;//代表小于目标值区域的头和尾ListNode h1 = null;ListNode t1 = null;//代表大于等于目标值的头和尾ListNode h2 = null;ListNode t2 = null;//用于保存head的下一个节点//注意：这里最后拼接好了以后，小于区域的头就是整个链表的新的头节点，因此，head可以作为遍历链表的指针。ListNode next = head.next;while (head != null) {//遍历next = head.next;head.next = null;if (head.val < x) {//如果当前节点的val小于目标值if (h1 == null) {//如果当前节点是小于区域的第一个节点h1 = head;t1 = head;} else {t1.next = head;t1 = head;}} else {if (h2 == null) {//如果当前节点是大于区域的第一个节点h2 = head;t2 = head;} else {//其他情况就把该节点尾插法插入链表中t2.next = head;t2 = head;}}head = next;}//进行小于区域链表和大于等于区域链表的拼接if (h2 == null) {//如果没有大于等于区域return h1;}if (h1 == null) {//如果没有小于区域return h2;}//如果两种区域都有，则让小于区域的尾指针指向大于等于区域的头指针t1.next = h2;return h1;}
}

2.4 随机链表的赋值

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {//创建一个map，key为老链表的节点。val为新链表的节点HashMap<Node,Node> map = new HashMap<Node,Node>();Node cur = head;//遍历链表，设置map的key和valuewhile(cur != null){map.put(cur,new Node(cur.val));cur = cur.next;}cur = head;//再次遍历老链表，给新链表设置每一个节点的next和randomwhile(cur != null){//cur 老链表节点//map.get(cur) cur对应的新链表map.get(cur).next = map.get(cur.next);//设置新链表的nextmap.get(cur).random = map.get(cur.random);//设置新链表的randomcur = cur.next;}return map.get(head);}
}

2.5环形链表的判断

方法一：利用HashSet集合。

思路：遍历当前链表，每次遍历判断当前节点是否已经存在于set集合中。如果不存在，则把当前节点放入集合。如果已经存在，说明当前节点就是第一个入环节点。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {//创建一个set，用于存放链表中已经遍历了的节点HashSet<ListNode> set = new HashSet<>();while(head != null){//如果当前节点已经存在于set，说明存在环形结构if(set.contains(head)) return true;set.add(head);head = head.next;}return false;}
}

方法二：快慢指针

开始时，快慢指针都在头节点的位置。快指针一次走两步，慢指针一次走一步。

如果没有环结构，快指针一定先走到尾节点。

如果有环结构，快慢指针会在换里相遇。而相遇所要走的卷数不会大于两圈。

相遇以后，快指针/慢指针到头节点的位置。两个指针开始一次走一步。最终两个指针会在第一次入换节点相遇！(原理就不证明了)

/*** 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 || head.next.next == null) return null;//定义慢指针，一次走一步ListNode n1 = head.next;//定义快指针，一次走两步ListNode n2 = head.next.next;while(n1 != n2){//当n1 n2不相遇时循环，所以我开始时没有把两个指针都设置在头节点的位置if(n2.next == null || n2.next.next == null){//说明没有环结构，直接返回空return null;}n1 = n1.next;//慢指针一次走一步n2 = n2.next.next;//慢指针一次走两步}//快指针移到头节点，开始一次走一步n2 = head;while(n1 != n2){//当两个指针相遇时，就走到了第一个入环节点n1 = n1.next;n2 = n2.next;}return n1;}
}

2.6 链表相交

思路：两个单链表，如何判断有没有相交点呢？

1.先遍历两个链表，到尾节点时停止。如果这时候，两个链表的尾节点都不想等。说明二者不相交。

2.如果二者尾节点是同一个，则计算二者链表长度的差值。让长的链表先走差值个距离。然后，短的链表从头开始走，二者一定会在相交点相遇！

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//定义两个指针用于遍历两条链表ListNode cur1 = headA;ListNode cur2 = headB;int n = 0;//用于记录两条链表的差值while(cur1.next != null){cur1 = cur1.next;n++;}while(cur2.next != null){cur2 = cur2.next;n--;}if(cur1 != cur2){//尾节点都不想等，说明二者不相交return null;}//这样遍历完两条链表，n就是两条链表的长度差cur1 = n > 0 ? headA : headB;//让cur1指向两条链表中长的那一条cur2 = cur1 == headA ? headB : headA;//让cur2指向两条链表中短的那一条n = Math.abs(n);//n取绝对值while(n != 0){//让长的那条链表先移动两条链表差值的距离，再一起走，就会在相交部分汇合！cur1 = cur1.next;n--;}while(cur1 != cur2){cur1 = cur1.next;cur2 = cur2.next;}return cur1;}
}

2.7.两数相加

思路：

/*** 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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode res = new ListNode();ListNode cur = res;int carry = 0;//当l1、l2中有一个不是空节点，或者还有进位，就继续循环while (l1 != null || l2 != null || carry != 0) {if (l1 != null) carry += l1.val;if (l2 != null) carry += l2.val;cur.next = new ListNode(carry % 10);//carry%10 就是该点的valcur = cur.next;carry = carry / 10;// carry/10 就是下一个点的进位if (l1 != null) l1 = l1.next;//l1 没有遍历完if (l2 != null) l2 = l2.next;}return res.next;}
}

2.8.合并两个有序链表

/*** 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 res = new ListNode();ListNode cur = res;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {//如果l1链表的值更小cur = cur.next = list1;list1 = list1.next;} else {cur = cur.next = list2;list2 = list2.next;}}while (list1 != null) {//如果1还没遍历完cur = cur.next = list1;list1 = list1.next;}while (list2 != null) {//如果2还没遍历完cur = cur.next = list2;list2 = list2.next;}return res.next;}
}

2.9 反转链表2

题解参考：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 reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(0, head);ListNode g = dummy;ListNode p = dummy;//g指向的下一个节点就是要开始反转的节点for (int i = 0; i < left - 1; i++) {g = g.next;p = p.next;}//p指向第left个节点p = p.next;for (int i = 0; i < right - left; i++) {ListNode temp = p.next;p.next = p.next.next;temp.next = g.next;g.next = temp;}return dummy.next;}
}

2.10.K个一组反转链表

        本题思路和上一题差不多。举一反三，还是主要用g、p两个指针反转链表。

        每组链表反转之前，g的next指向的都是待反转链表的第一个节点，p指向的就是待反转链表的第一个节点。
        要注意的就是每次反转完链表p指针指向的就是反转后链表的最后一个元素，同时它的next也是下一组待反转链表的第一个元素，所以每次每组反转完以后，都要把p赋值给g。

/*** 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 dummy = new ListNode(0, head);ListNode g = head;//计算一共有多少个节点，用来算要反转几组链表int count = 0;while (g != null) {g = g.next;count++;}g = dummy;ListNode p = g.next;//遍历for (int i = 0; i < count / k; i++) {p = g.next;//反转的每组链表for (int j = 1; j < k; j++) {ListNode temp = p.next;p.next = p.next.next;temp.next = g.next;g.next = temp;}//每组链表反转完，让cur的next指向下一组待反转链表第一个g = p;}return dummy.next;}
}