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;//值不相同，直接返回false
head = 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初始化为null
ListNode pre = null;
while(cur != null){//当元素还没遍历完的时候
//在cur指向pre前，用于保存cur.next，防止链表找不到了。
ListNode temp = cur.next;
//让当前节点cur，指向pre
cur.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和value
while(cur != null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
//再次遍历老链表，给新链表设置每一个节点的next和random
while(cur != null){
//cur 老链表节点
//map.get(cur) cur对应的新链表
map.get(cur).next = map.get(cur.next);//设置新链表的next
map.get(cur).random = map.get(cur.random);//设置新链表的random
cur = 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 就是该点的val
cur = 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;
}
}