链表
反转链表
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ import java.util.Stack; public class Solution { public ListNode ReverseList(ListNode head) { Stack<ListNode> stack = new Stack<>(); //把链表节点全部摘掉放到栈中 while (head != null) { stack.push(head); head = head.next; } //判断链表不为空 if (stack.isEmpty()) return null; //获取栈顶的第一个节点 ListNode node = stack.pop(); //用于返回的节点，先通过下面的while循环构造链表再返回节点 ListNode dummy = node; //栈中的结点全部出栈，然后重新连成一个新的链表 while (!stack.isEmpty()) { //取出栈顶元素（注意这是原本栈的第二个元素开始取，前面已经取了一个） ListNode tempNode = stack.pop(); //把当前节点指针的指向下一个元素 node.next = tempNode; //把当前节点变成下一个节点，继续遍历 node = node.next; } //最后一个结点就是反转前的头结点，一定要让他的next //等于空，否则会构成环 node.next = null; return dummy; } }
*链表内指定区间反转
import java.util.*; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { ListNode dummy = new ListNode(-1); // 哑巴节点，指向链表的头部 dummy.next = head; ListNode pre = dummy; // pre 指向要翻转子链表的前驱节点 for (int i = 1; i < m; ++i) { pre = pre.next; } head = pre.next; // head指向翻转子链表的首部 ListNode next; for (int i = m; i < n; ++i) { next = head.next; // head节点连接next节点之后链表部分，也就是向后移动一位 head.next = next.next; // next节点移动到需要反转链表部分的首部 next.next = pre.next; // pre继续为需要反转头节点的前驱节点 pre.next = next; } return dummy.next; } }
合并两个排序的链表
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { //如果有一个链表为空，返回另一个链表（特殊情况） if(list1 == null || list2 == null){ return list1 != null ? list1 : list2; } /** 两个链表元素依次对比（其实只需要改变链表元素指针的指向就可以了） 链表1的第一个元素小于链表2的第一个元素就把链表1的第一个元素放在第一个 然后递归调用Merge方法来比较链表1的第二个元素和链表2的第一个元素，以此类推 反之也一样，只是两个链表的顺序倒过来 **/ if(list1.val <= list2.val){ // 递归计算 list1.next, list2 list1.next = Merge(list1.next, list2); return list1; }else{ // 递归计算 list1, list2.next list2.next = Merge(list1, list2.next); return list2; } } }
判断链表中是否有环
知识点：双指针
双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个指针（特殊情况甚至可以多个），两个指针或是同方向访问两个链表、或是同方向访问一个链表（快慢指针）、或是相反方向扫描（对撞指针），从而达到我们需要的目的。
思路
我们都知道链表不像二叉树，每个节点只有一个val值和一个next指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那这时我们就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。为什么这样说呢？仔细看上图，在环2，0，-4中，没有任何一个节点可以指针指出环，它们只能在环内不断循环，因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。
但是，环形链表遍历过程中会不断循环，线形链表遍历到NULL结束了，但是环形链表何时能结束呢？我们可以用双指针技巧，同向访问的双指针，速度是快慢的，只要有环，二者就会在环内不断循环，且因为有速度差异，二者一定会相遇。
具体做法
step 1：设置快慢两个指针，初始都指向链表头。
step 2：遍历链表，快指针每次走两步，慢指针每次走一步。
step 3：如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。
step 4：如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public boolean hasCycle(ListNode head) { //先判断链表为空的情况 if (head == null) return false; //快慢双指针 ListNode fast = head; ListNode slow = head; //快指针还没到达末尾的时候 while (fast != null && fast.next != null) { //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环 if (fast == slow) return true; } //到末尾则没有环 return false; } }
链表中环的入口结点
快慢指针方法
通过定义slow和fast指针，slow每走一步，fast走两步，若是有环，则一定会在环的某个结点处相遇（slow == fast），根据下图分析计算，可知从相遇处到入口结点的距离与头结点与入口结点的距离相同。
具体做法
step 1：判断链表中是否有环中的方法判断链表是否有环，并找到相遇的节点。
step 2：慢指针继续在相遇节点，快指针回到链表头，两个指针以相同的速度逐个元素逐个元素开始遍历链表。
step 3：再次相遇的地方就是环的入口。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if (pHead == null) return null; // 定义快慢指针 ListNode slow = pHead; ListNode fast = pHead; while (fast != null && fast.next != null) { // 快指针是满指针的两倍速度 fast = fast.next.next; slow = slow.next; // 记录快慢指针第一次相遇的结点 if (slow == fast) break; } // 若是快指针指向null，则不存在环 if (fast == null || fast.next == null) return null; // 重新指向链表头部 fast = pHead; // 与第一次相遇的结点相同速度出发，相遇结点为入口结点 while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }
链表中倒数最后k个结点
思路
我们无法逆序遍历链表，就很难得到链表的倒数第kkk个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第kkk的位置上，即距离链表尾的距离是kkk，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是kkk。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施。
具体做法
step 1：准备一个快指针，从链表头开始，在链表上先走k步。
step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { int n = 0; ListNode fast = pHead; ListNode slow = pHead; //快指针先行k步 for (int i = 0; i < k; i++) { if (fast != null) fast = fast.next; //达不到k步说明链表过短，没有倒数k else return slow = null; } //快慢指针同步，快指针先到底，慢指针指向倒数第k个 while (fast != null) { fast = fast.next; slow = slow.next; } //上面的while循环就是找到倒数的第k个节点，也就是慢指针指向的节点，所以返回慢指针就好了 //（注意这里可能是一个很短的链表，因为慢节点有next指针指向后面的节点） return slow; } }
删除链表的倒数第n个节点
具体做法
step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
step 2：准备一个快指针，在链表上先走n步。
step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是n。
step 4：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数n个元素的位置。
step 5：最后将该节点前序节点的指针指向该节点后一个节点，删掉这个节点。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { public ListNode removeNthFromEnd (ListNode head, int n) { //添加表头是为了方便处理第一个节点给删除了的情况 ListNode res = new ListNode(-1); res.next = head; //当前节点/慢节点 ListNode cur = head; //前序节点 ListNode pre = res; ListNode fast = head; //快指针先行n步 while (n != 0) { fast = fast.next; n--; } //快慢指针同步，快指针到达末尾，慢指针就到了倒数第n个位置 while (fast != null) { fast = fast.next; pre = cur; cur = cur.next; } //删除该位置的节点 pre.next = cur.next; //返回链表的头指针（也就是头指针指向的第一个节点） return res.next; } }
两个链表的第一个公共结点
解题思路
使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。
让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1的头节点继续遍历，也就是说，N1和N2都会遍历链表1和链表2。
因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。
（N1最后肯定能到达链表2的终点，N2肯定能到达链表1的终点）。
如何得到公共节点：
- 有公共节点的时候，N1和N2必会相遇，因为长度一样嘛，速度也一定，必会走到相同的地方的，所以当两者相等的时候，则会第一个公共的节点
- 无公共节点的时候，此时N1和N2则都会走到终点，那么他们此时都是null，所以也算是相等了。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode l1 = pHead1, l2 = pHead2; while (l1 != l2) { l1 = (l1 == null) ? pHead2 : l1.next; l2 = (l2 == null) ? pHead1 : l2.next; } return l1; } }
*链表相加
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
从这个例子我们可以得到：
1、两个链表的长度可能不等，需要对齐
2、相加后可能需要进位
对齐进位
因为我们无法保证两个链表长度一致，所以我们干脆从后往前对齐，跟我们整数再做加法一样
所以我们的入手则是对链表进行对齐，我们可以看到上面的图片，我们都是从后面开始对齐与计算的，所以很容易想到反转链表后进行相加。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList (ListNode head1, ListNode head2) { // 进行判空处理 if (head1 == null) return head2; if (head2 == null) { return head1; } // 反转h1链表 head1 = reverse(head1); // 反转h2链表 head2 = reverse(head2); // 创建新的链表头节点 ListNode head = new ListNode(-1); ListNode nHead = head; // 记录进位的数值 int tmp = 0; while (head1 != null || head2 != null) { // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值） int val = tmp; // 当节点不为空的时候，则需要加上当前节点的值 if (head1 != null) { val += head1.val; head1 = head1.next; } // 当节点不为空的时候，则需要加上当前节点的值 if (head2 != null) { val += head2.val; head2 = head2.next; } // 求出进位 tmp = val / 10; // 进位后剩下的数值即为当前节点的数值 nHead.next = new ListNode(val % 10); // 下一个节点 nHead = nHead.next; } // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位 if (tmp > 0) { nHead.next = new ListNode(tmp); } // 重新反转回来返回 return reverse(head.next); } // 反转链表 ListNode reverse(ListNode head) { if (head == null) return head; ListNode cur = head; ListNode node = null; while (cur != null) { ListNode tail = cur.next; cur.next = node; node = cur; cur = tail; } return node; } }
单链表的排序
具体做法
step 1：遍历链表，将节点值加入数组。
step 2：使用内置的排序函数对数组进行排序。
step 3：依次遍历数组和链表，按照位置将链表中的节点值修改为排序后的数组值。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { public ListNode sortInList (ListNode head) { ArrayList<Integer> nums = new ArrayList<>(); ListNode p = head; //遍历链表，将节点值加入数组 while (p != null) { nums.add(p.val); p = p.next; } //上面的while循环以后p指向链表最后一个元素，所以这里要把p重新指向头结点，方便后面的for循环 p = head; //对数组元素排序 Collections.sort(nums); //遍历数组 for (int i = 0; i < nums.size(); i++) { //将数组元素依次加入链表 p.val = nums.get(i); p = p.next; } return head; } }
判断一个链表是否为回文结构
思路
即然回文结构正序遍历和逆序遍历结果都是一样的，我们是不是可以尝试将正序遍历的结果与逆序遍历的结果一一比较，如果都是对应的，那很巧了！它就是回文结构！
这道题看起来解决得如此之快，但是别高兴太早，链表可没有办法逆序遍历啊。链表由前一个节点的指针指向后一个节点，指针是单向的，只能从前面到后面，我们不能任意访问，也不能从后往前。但是，另一个容器数组，可以任意访问，我们把链表中的元素值取出来放入数组中，然后判断数组是不是回文结构，这不是一样的吗？
具体做法
step 1：遍历一次链表，将元素取出放入辅助数组中。
step 2：准备另一个辅助数组，录入第一个数组的全部元素，再将其反转。
step 3：依次遍历原数组与反转后的数组，若是元素都相等则是回文结构，只要遇到一个不同的就不是回文结构。
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { public boolean isPail (ListNode head) { ArrayList<Integer> nums = new ArrayList(); //将链表元素取出一次放入数组 while(head != null){ nums.add(head.val); head = head.next; } ArrayList<Integer> temp = new ArrayList(); temp = (ArrayList<Integer>) nums.clone(); //准备一个数组承接翻转之后的数组 Collections.reverse(temp); for(int i = 0; i < nums.size(); i++){ int x = nums.get(i); int y = temp.get(i); //正向遍历与反向遍历相同 if(x != y) return false; } return true; } }
这了注意上面不能像上面这样简写，有部分数据会出错
