两数之和
// 这里创建一个新的链表，是因为必须创建一个指针，来输出结果集，或者只新建一个指针来保证记录链表的关系也可。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = l1,q = l2;
int c = 0;
ListNode head = new ListNode(0);
ListNode r = head;
while (p != null || q != null || c > 0){
int pValue = p == null ? 0 : p.val;
int qValue = q == null ? 0 : q.val;
int sum = pValue + qValue + c ;
r.next = new ListNode(sum % 10);
r = r.next;
c = sum / 10;
p = p == null ? null: p.next;
q = q == null ? null: q.next;
}
r.next = null;
return head.next;
}
删除倒数第n个节点
// 为了找到倒数第n个，先让一个节点先走，当以一个节点到结尾时，第二个节点的下一个就是倒数第n个节点，直接 q.next = q.next.next;跳过第n个，这里一定要创建头节点，因为可能会删除头节点，则没办法找到头，或者就会与其他操作不一致。
public ListNode removeNthFromEnd(ListNode head, int n) {
// 使用快慢指针
// 这里必须创建头结点，防止删除第一个节点
ListNode Head = new ListNode(0);
Head.next = head;
ListNode p = Head,q = Head;
while (p != null && n > 0){
p = p.next;
n --;
}
while (p != null && p.next != null){
q = q.next;
p = p.next;
}
q.next = q.next.next;
return Head.next;
}
合并两个单链表
遍历一遍，谁小选谁，然后剩下还有的直接进行指向
迭代合并好理解
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p = l1; ListNode q = l2;
ListNode head = new ListNode(0);
ListNode r = head;
while (p != null && q != null){
int date = p.val >= q.val ? q.val : p.val;
r.next = new ListNode(date);
r = r.next;
if ( p.val < q.val){
p = p.next;
}else {
q = q.next;
}
}
if (p != null){
r.next = p;
}else {
r.next = q;
}
return head.next;
}
// 递归合并的做法
// 递归合并
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null){
return l2;
}else if (l2 == null){
return l1;
}
// 两个都不null的情况
if (l1.data < l2.data){
// 现在选l1，用l1的next找寻下一个节点
l1.next = mergeTwoLists2(l1.next,l2);
return l1;
}else {
l2.next = mergeTwoLists2(l1,l2.next);
return l2;
}
}
合并K个排序链表
直接对K个排序链表进行两两合并，调用两两合并的方法
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p = l1; ListNode q = l2;
ListNode head = new ListNode(0);
ListNode r = head;
while (p != null && q != null){
int date = p.val >= q.val ? q.val : p.val;
r.next = new ListNode(date);
r = r.next;
if ( p.val < q.val){
p = p.next;
}else {
q = q.next;
}
}
if (p != null){
r.next = p;
}else {
r.next = q;
}
return head.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0){
return null;
}
int n = lists.length;
if (n == 1){
return lists[0];
}
ListNode list = lists[0];
for (int i=1;i<n;i++){
list = mergeTwoLists(list, lists[i]);
}
return list;
}
// 使用分治的两两合并
// 让两两合并于第一个列表，然后再次分割进行两两合并，每次合并进行乘2，进行分治的合并
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0){
return null;
}
int n = lists.length;
int interval = 1;
while (interval < n){
for (int i=0;i<n-interval;i+= interval*2){
lists[i] = mergeTwoLists(lists[i],lists[i+interval]);
}
interval *= 2;
}
return lists[0];
}
两两交换链表中的节点
思路是： 如果当前只有一个节点直接返回null, 或者当前只有一个节点不用交换直接返回
使用递归思想， 当前头节点指向下一个交换后返回的头， 第二个节点指向第一个节点，返回第二个节点作为头
public ListNode swapPairs(ListNode head) {
if (head == null || head != null && head.next == null){
return head;
}
ListNode p = head; ListNode q = head.next;
p.next = swapPairs(q.next);
q.next = p;
return q;
}
// 使用迭代进行交换相邻的节点
思路： 创建头节点， 初始维持三个指针 头，第一个指针，第二个指针，当 第二个指针不等于null, 头的next 指向第二个节点， 第一个指针，指向第二个节点的next,
第二个节点next,指向第一个节点。 头变为第一个节点，第一个节点变为自己的next,next变为cur更改后的next，注意这里要判空
主要是第一个节点会成为下一个对的 头节点
// 使用迭代
public ListNode swapPairs2(ListNode head){
if (head == null || head.next == null){
return head;
}
// 迭代必须创建头节点
ListNode Head = new ListNode(-1);
Head.next = head;
for (ListNode pre = Head,cur = Head.next,next = head.next;next != null;
pre = cur,cur = cur.next,next = cur != null ? cur.next : null){
pre.next = next;
cur.next = next.next;
next.next = cur;
}
return Head.next;
}
K个一组翻转链表
和两个反转迭代的思路是一样的， 让头节点指向下次反转的递归，整个进行迭代，注意保证下一个是否可以取到迭代
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null|| k <= 1 ){
return head;
}
ListNode r = head;
int c = k;
while (r != null && --k > 0){
r = r.next;
}
if (k != 0){
return head;
}
ListNode q = head.next;
ListNode p = head;
ListNode s = q.next;
head.next = reverseKGroup(r.next, c);
while (p != r){
q.next = p;
p = q;
q = s;
s =s == null ? null :s.next;
}
return r;
}
// 反转， 首先通过计数找到end, 如果 end == null,直接break, 否则记录start,和下一个next
end.next = null, 将start进入反转方法，pre .next = 反转头，反转的尾，也就是start.next 指向下一个节点的next,最后end =头
public ListNode reverseKGroup2(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
ListNode start = pre.next;
// 标记了 end 的next 直接end 为 null
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return dummy.next;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
旋转链表
这里主要主要旋转的时候判断是否超出了原有的链表的长度，需求进行取mod
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0){
return head;
}
ListNode p = head;
int len = 0;
while (p != null){
len ++;
p = p.next;
}
p = head; k = k % len;
ListNode q = head;
while (head != null && k-- > 0){
p = p.next;
}
while (p!= null && p.next != null){
p = p.next;
q = q.next;
}
p.next = head;
ListNode root = q.next;
q.next = null;
return root;
}
删除重复的链表节点2
// 思路是 使用一个指针维护当前的链表，另一个指针来跳过重复元素，判断当前元素是否等于下一个元素，否则记录，并循环跳过值等于记录值得元素。
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode root = new ListNode(0);
root.next = head;
ListNode p = root, q = head;
while(q != null){
while(q!= null && q.next != null && q.val == q.next.val){
int data = q.val;
q = q.next;
while(q!= null && data == q.val){
q = q.next;
}
}
p.next = q;
p = p.next;
q = q== null? null:q.next;
}
return root.next;
}
// 递归写法
// 递归写法
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
if(head.next != null && head.val == head.next.val){
while(head != null && head.next != null && head.val == head.next.val){
head = head.next;
}
return deleteDuplicates(head.next);
}else{
head.next = deleteDuplicates(head.next);
return head;
}
}
删除重复元素
// 递归版本
// 递归
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
if(head.next != null && head.val == head.next.val){
while(head != null && head.next != null &&
head.val == head.next.val){
head = head.next;
}
head.next = deleteDuplicates(head.next);
}else{
head.next = deleteDuplicates(head.next);
}
return head;
}
// 迭代的方法
// 迭代
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode p = head;
ListNode q = head.next;
while(q != null){
while(q != null && p.val == q.val){
q = q.next;
}
p.next = q;
p = p.next;
q = q == null ? null : q.next;
}
return head;
}
分割链表
// 将大的放大左边，小的放到右边，使用双链表
public ListNode partition(ListNode head, int x) {
if (head == null) {
return head;
}
ListNode before_list = new ListNode(0);
ListNode p = before_list;
ListNode after_list = new ListNode(0);
ListNode q = after_list;
while (head != null){
if (head.data < x){
p.next = new ListNode(head.data);
p = p.next;
}else {
q.next = new ListNode(head.data);
q = q.next;
}
head = head.next;
}
q.next = null;
p.next = after_list.next;
return before_list.next;
}
反转链表2
思路： 创建头节点，让pre和 end都指向头节点，找到第n前一个和第m个节点，
标记 start = pre.next, next = end.next; end.next = null
然后让 pre.next = 指向反转后的首节点
start自然变为返回后的尾节点， start.next = next 维持链表
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
// pre 标记直接的节点
ListNode pre = dummy;
ListNode end = dummy;
for (int i=0;i<n && end != null;i++){
end = end.next;
}
for (int i=0;i<m-1 && pre != null;i++){
pre = pre.next;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
return dummy.next;
}
private ListNode reverse(ListNode head){
ListNode pre = null;
ListNode curr = head;
while (curr != null){
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}
// 递归反转
private boolean stop;
private ListNode left;
public void recurseAndReverse(ListNode right, int m, int n) {
if (n == 1) {
return;
}
right = right.next;
if (m > 1) {
this.left = this.left.next;
}
this.recurseAndReverse(right, m - 1, n - 1);
if (this.left == right || right.next == this.left) {
this.stop = true;
}
if (!this.stop) {
int t = this.left.val;
this.left.val = right.val;
right.val = t;
this.left = this.left.next;
}
}
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
this.recurseAndReverse(head, m, n);
return head;
}
将有序链表转换为二叉搜索树
思路是使用快慢指针找到中间节点，注意，可以不让快指针走的链表的头，这样就会找到中间节点的前一个节点，方便之后的断开和重复迭代的操作
// 思路 找到中间节点 使用快慢指针，找到中间节点，将 其 断开 ， 再次迭代左右节点
public TreeNode sortedListToBST(ListNode head) {
if (head == null){
return null;
}else if(head.next == null){
return new TreeNode(head.val);
}
// 创建头节点
ListNode root = new ListNode(0);
root.next = head;
// 创建快慢指针
ListNode fast = root, slow = root;
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode node = slow.next;
TreeNode T = new TreeNode(node.val);
slow.next = null;
T.left = sortedListToBST(head);
T.right = sortedListToBST(node.next);
return T;
}
// 模拟中序遍历来创建二茬搜索树
ListNode head;
public TreeNode sortedListToBST(ListNode head){
// 求链表的长度
int size = findSize(head);
// 保存当前的节点
this.head = head;
return convertList(0,size-1);
}
private TreeNode convertList(int l, int r) {
if (l > r){
return null;
}
int mid = l + (r - l)/2;
TreeNode left = convertList(l,mid-1);
TreeNode root = new TreeNode(head.val);
root.left = left;
head = head.next;
root.right = convertList(mid+1,r);
return root;
}
private int findSize(ListNode head) {
int count = 0;
while (head != null){
count ++;
head = head.next;
}
return count;
}
找到环形链表入口点
这里一定不要使用val进行比较，a = c
// 环形链表 2
public ListNode detectCycle(ListNode head) {
if (head == null){
return head;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow){
break;
}
}
if (fast == null || fast.next == null){
return null;
}
fast = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
链表头尾重排序
思路找到中间节点，将中间节点后的节点入栈，然后再次遍历每次遍历插入一个栈中节点
/ 思路： 使用栈装入后一半的节点，逆序输出
public void reorderList(ListNode head) {
if (head == null){
return;
}
if (head.next == null){
return;
}
ListNode fast = head, slow = head;
while (head.next != null head.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
// stack
Stack<ListNode> stack = new Stack<>();
ListNode end = slow.next;
while (slow != null){
slow = slow.next;
stack.push(slow);
}
// 出站
ListNode p = new ListNode(0);
ListNode next = head;
while (next != end){
p.next = next;
p = p.next;
next = p.next;
if (!stack.empty()) {
p.next = stack.pop();
p = p.next;
}
}
while (!stack.empty()){
p.next = stack.pop();
p = p.next;
}
p.next = null;
}
// 使用递归的思路进行逆向遍历链表
左指针的实现是通过全局变量来实现
// 递归的思路是全局变量记录左指针，迭代的回溯记录右指针，同时使用flag，来保证结束后不在执行回溯的操作
boolean flag = false;
ListNode left;
public void reorderList(ListNode head){
if (head == null){
return;
}
this.left = head;
orderList(head);
}
public void orderList(ListNode right){
if (right == null){
return;
}
orderList(right.next);
if (left == right || right.next == left){
flag = true;
left.next = null;
}
if (!flag){
ListNode success = left.next;
right.next = success;
left.next = right
left = success;
}
}
链表的插入排序
这里注意才选择要插入的节点时，如果不需要进行插入的才会往后移动，否则不进行移动
public ListNode insertionSortList(ListNode head) {
if (head == null){
return head;
}
ListNode root = new ListNode(0);
root.next = head;
ListNode node;
for (ListNode p = head;p.next != null;){
if (p.next.data < p.data) {
node = p.next;
p.next = p.next.next;
for (ListNode r = root; r != p; r = r.next) {
if (node.data < r.next.data){
node.next = r.next;
r.next = node;
break;
}
}
}else {
p = p.next;
}
}
return root.next;
}
链表排序（归并排序）
使用迭代归并排序进行链表排序
public ListNode sortList(ListNode head){
// 如果头为空，或者只有一个节点，直接返回
if (head == null || head.next == null){
return head;
}
// 找到中间节点,使用fast比slow快一个节点的方法
ListNode fast = head.next,slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode next = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(next);
// 合并
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null){
if (left.val < right.val){
res.next = left;
left = left.next;
}else {
res.next = right;
right = right.next;
}
res = res.next;
}
// 最后不为null 再拼接上
res.next = left == null ? right : left;
return h.next;
}
```
#### 回溯判断是否回文
```
// 使用回溯轻松完成回文，或者用栈进行存储，然后再次遍历
ListNode left;
boolean stop = false;
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null){
return true;
}
this.left = head;
return checkPalin(head);
}
public boolean checkPalin(ListNode right){
if (right == null){
return true;
}
boolean flag = checkPalin(right.next);
if (flag == false){
return false;
}
if (left == right || right.next == left){
stop = true;
left.next = null;
return true;
}
if (!stop){
if (left.data != right.data){
return false;
}
this.left = left.next;
}
return true;
}
```
// 在找到中间节点的同时顺便把前半部分进行反转
// 这里slow 和 fast 并驾齐驱出发，那么slow所到达的点是下一半的起点，否则fast快slow一步slow到达是上一半终点
##### 这里注意一点需要判断 链表的个数是不是奇数个主要采用判断fast是不是为null,在一同出发的时候，如果fast 为 null 说明为偶数，fast不为null，说明链表个数为奇数个。
```
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
```
#### 分割链表
思路是将 计算总数，计算求余的数，然后进行遍历截断，并赋值
```
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] listNodes = new ListNode[k];
// 获得链表长度
int len = getListLen(root);
// 获得每部分长度
int perLen = len/k-1;
int modLen = len > k ? len%k : 0;
// 添加进结果集
for (int i=0;i<k;i++){
int l = modLen > 0 ? perLen + 1 : perLen;
modLen --;
if (root == null){
listNodes[i] = null;
}else {
int j = 0;
ListNode p = root;
ListNode h = root;
while (p != null && j < l){
j++;
p = p.next;
}
root = p == null?null:p.next;
if(p != null){
p.next = null;
}
listNodes[i] = h;
}
}
return listNodes;
}
public int getListLen(ListNode root){
if (root == null){
return 0;
}
int count = 0;
while (root != null){
count ++;
root = root.next;
}
return count;
}
```
#### 两数相加2
```
// 链表两数相加思路： 首先计算两个链表的长度，然后在短的前面补0，然后递归相加，注意在进行递归时创建好链表的节点，
// 回溯时添加值，并判断返回的上一个节点是否大于 10 ，最终大于10 再添加个节点
// 可不可以使用回溯进行两数相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Size = listSize(l1);
int l2Size = listSize(l2);
if (l1Size - l2Size > 0) {
l2 = headFillZero(l2, l1Size - l2Size);
} else {
l1 = headFillZero(l1, l2Size - l1Size);
}
ListNode node = addTwoNumbers(l1, l2, new ListNode(-1));
if (node.val >= 10) {
ListNode newNode = new ListNode(node.val % 10);
node.val = node.val / 10;
newNode.next = node.next;
node.next = newNode;
}
return node;
}
public static ListNode addTwoNumbers(ListNode l1, ListNode l2, ListNode head) {
if (l1.next == null && l2.next == null) {//遇见l1和l2的最后两个节点，相加返回
head.next = new ListNode(l1.val + l2.val);
return head.next;
}
head.next = new ListNode(-1);//先构建好一个节点追加在head后面，具体val在递归返回阶段依次计算填充.
head = head.next;
ListNode node = addTwoNumbers(l1.next == null ? l1 : l1.next, l2.next == null ? l2 : l2.next, head);
int temp = l1.val + l2.val + node.val / 10;//计算当前节点的值，node.val是上一个节点的值，如果node.val大于10，则进位计算.
node.val = node.val % 10;//重新计算上一个节点的值.
head.val = temp;
return head;
}
public static int listSize(ListNode listNode) {
if (listNode == null) {
return 0;
}
int size = 0;
while (listNode != null) {
size++;
listNode = listNode.next;
}
return size;
}
public static ListNode headFillZero(ListNode node, int fillNum) {
if (fillNum == 0) {
return node;
}
ListNode head = node;
for (int i = 0; i < fillNum; i++) {
ListNode temp = head;
head = new ListNode(0);
head.next = temp;
}
return head;
}
```
#### 扁平化多级的双向链表
一直遍历，如果节点存在孩子节点，就存储下节点，然后将孩子节点拼接到这个链表中
```
// 判断 当前 是否存储孩子节点，记录node的next,找到根节点连接到写一个节点，
public Node flatten(Node head) {
if (head == null){
return head;
}
Node p = head;
while (p != null){
// 存储下一个节点
Node tmp = p.next;
if (p.child != null){
p.next = p.child;
p.child.prev = p;
// 获取 孩子的结束节点
Node node = getChildTail(p.child);
node.next = tmp;
if (tmp != null)
tmp.prev = node;
}
p.child = null;
p = p.next;
}
return head;
}
public Node getChildTail(Node node){
if (node.next == null){
return node;
}
return getChildTail(node.next);
}
```
#### 链表中下一个更大的节点
// 使用回溯 + 栈
```
// 设计一个最大栈大于当前入栈否则将当前值再次入栈
Stack<Integer> stack = new Stack<>();
public int[] nextLargerNodes(ListNode head) {
return nextLargerNodes(head,0);
}
public int[] nextLargerNodes(ListNode head, int i){
if (head == null){
stack.push(0);
int[] res = new int[i];
return res;
}
int[] res = nextLargerNodes(head.next, i + 1);
while (!stack.empty() && stack.peek() <= head.data){
stack.pop();
}
res[i] = stack.empty()?0:stack.peek();
stack.push(head.data);
return res;
}
```
// 迭代 不使用 回溯也可以
使用双栈， 在计算哪一个 值的下一个最大时
一次将节点添加进栈，然后在从后进行弹出，招待比当前节点大的
```
public static int[] nextLargerNodes(ListNode head) {
if (head.next == null) {
return new int[] {0};
}
Stack<Integer> input = new Stack<>();
int size = 0;
while (head != null) {
size ++;
input.push(head.val);
head = head.next;
}
Stack<Integer> stack = new Stack<>();
int[] result = new int[size];
while (!input.isEmpty()) {
size--;
while (!stack.isEmpty() && input.peek() >= stack.peek()) {
stack.pop();
}
if (stack.isEmpty()) {
result[size] = 0;
} else {
result[size] = stack.peek();
}
stack.push(input.pop());
}
return result;
}
```
网友评论