21. 合并两个有序链表
/** * 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 l1 = list1; ListNode l2 = list2; // 新链表头指针 ListNode header = null; // 新链表后指针 ListNode before = null; // 特别注意示例 [1,5] [1,2,4] while(l1 != null || l2 != null) { // 两者都没走到末尾,都不为空 if (l1 != null && l2 != null) { // 两链表当前节点相同,加两个一样的到新链表,并同时向前走一步 if (l1.val == l2.val) { ListNode newNode1 = new ListNode(l1.val); ListNode newNode2 = new ListNode(l2.val); if (before != null) { before.next = newNode1; } newNode1.next = newNode2; before = newNode2; // 两个相等,同时加入新链表,同时向前走一步 l1 = l1.next; l2 = l2.next; // 新链表头节点,只在为 null 的时候指定一次 if (header == null) { header = newNode1; } } // 两链表当前节点不同,加小的那个到新链表,并只将小的那个向前走一步 else { ListNode newNode = null; if (l1.val < l2.val) { newNode = new ListNode(l1.val); // l1 当前比 l2 当前小,只把 l1 加入新链表,也只有 l1 向前走一步 l1 = l1.next; } else if (l2.val < l1.val) { newNode = new ListNode(l2.val); // l2 当前比 l1 当前小,只把 l2 加入新链表,也只有 l2 向前走一步 l2 = l2.next; } // 将新节点与之前的连上 if (before != null) { before.next = newNode; } before = newNode; // 新链表头节点,只在为 null 的时候指定一次 if (header == null) { header = newNode; } } } // 两链表有一者走到了末尾,将没走到末尾的那个当前节点加入新链表,并向前走一步 else { ListNode newNode = null; if (l1 != null && l2 == null) { // 只走还没走完的这个链表 newNode = new ListNode(l1.val); l1 = l1.next; } else if (l2 != null && l1 == null) { // 只走还没走完的这个链表 newNode = new ListNode(l2.val); l2 = l2.next; } // 将新节点与之前的连上 if (before != null) { before.next = newNode; } before = newNode; // 新链表头节点,只在为 null 的时候指定一次 if (header == null) { header = newNode; } } } return header; } }
25. K 个一组翻转链表
写一个反转链表的公共方法 revers(ListNode listHead)
ki 表示走到了 k 组第几个;k 组第一个记为 kStart ; k 组最后一个记为 kEnd;前一个 k 组的尾巴记为 preKTail
每次走到 k 组最后一个的时候
- ki 清零
- kEnd 指向 null ,调用反转方法反转 kStart
- 如果 preKTail 不为空,preKTail指向 kEnd,preKTail 变为 kStart (反转后 start 成了尾)
如果走到了末尾,而 ki >1 说明后面的不够 k 个一组,不用反转。因此 preKTail 直接指向 kStart
/** * 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 kStart = null; ListNode kCur = head; ListNode kEnd = null; ListNode preKtail = null; ListNode resHead = null; int ki = 1; while(kCur != null) { // 每次先缓存下一个节点,防止后面有变化 ListNode nextNode = kCur.next; if (ki == 1) { // k 个一组的起始 kStart = kCur; } if (ki == k) { kEnd = kCur; if (resHead == null) { resHead = kEnd; } ki=0; // 切断与下一个 k 组的联系,使得反转链表的时候有尾指向null kEnd.next = null; // 上一个链表尾指向这个的最后一个(待翻转) if (preKtail != null) { preKtail.next = kEnd; } // 反转链表 reverseList(kStart); // 链表已经反转过,头成了尾巴 preKtail = kStart; } ki++; kCur = nextNode; if (kCur == null && ki > 1) { // 没有任何完整的一组的情况 if (resHead == null) { resHead = kStart; } // 这些剩下的不用反转,因此上一个尾指向这一个头 if (preKtail != null) { preKtail.next = kStart; } break; } } return resHead; } private void reverseList(ListNode head) { ListNode cur = head; ListNode pre = null; while(cur != null) { // 先缓存下一个节点。注意怎么反转链表,这个 Next 指针要每次循环新生成一个,不能定义一个全局的 ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } } }
标签:ListNode,val,next,链表,l2,操作,null,LeetCode From: https://www.cnblogs.com/suBlog/p/17354453.html