目录
2. 两数相加
19. 删除链表的倒数第 N 个结点
21. 合并两个有序链表
23. 合并 K 个升序链表
24. 两两交换链表中的节点
2. 两数相加
https://leetcode.cn/problems/add-two-numbers/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//head是cur链表头节点，cur用于记录相加和的链表；
ListNode head = new ListNode();
ListNode cur = head;
//进位标志；
int flag = 0;
//两个用于相加的链表都走到null，结束；
while(l1!=null || l2!=null){
int l1Val = l1==null ? 0 : l1.val;
int l2Val = l2==null ? 0 : l2.val;
//计算和；
int sum = l1Val+l2Val+flag;
//新建节点加入cur链表中；
cur.next = new ListNode(sum%10);
//判断是否需要进位；
if(sum>=10){
flag=1;
}else {
flag=0;
}
//判断两个用于相加的链表是否走到null，没到的才继续走；
if(l1!=null){
l1 = l1.next;
}
if(l2!=null){
l2 = l2.next;
}
//cur链表也向后移动；
cur = cur.next;
}
//走到这里代表两个链表已经遍历完毕；
//但是可能最后一次相加也产生了进位，因此在这里要判断；
if(flag == 1){
cur.next = new ListNode(1);
}
//头节点是空值，返回头节点的下一节点；
return head.next;
}19. 删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
public ListNode removeNthFromEnd(ListNode head, int n) {
//创建快慢指针，两个指针的next为head；
ListNode fast = new ListNode();
ListNode slow = new ListNode();
fast.next = head;
slow.next = head;
//记录慢指针的头节点，用于返回；
ListNode root = slow;
//快指针先走n步；
for (int i=n;i>0;i--){
fast = fast.next;
//处理n大于链表长度的情况；
if(fast == null){
return null;
}
}
//依次移动快慢指针，直到快指针的next为null；
//此时代表慢指针到达要删除的元素的前一位值；
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
//删除下一元素；
slow.next = slow.next.next;
//返回；
return root.next;
}21. 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//创建头节点和一个用于移动的节点cur；
ListNode head = new ListNode(0);
ListNode cur = head;
//边移动，边比较节点的值，并将比较结果赋值，直到有一个链表走完；
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
//判断是哪个链表走完了，把另一个链表在尾部续上；
if(list1 == null){
cur.next = list2;
}
if(list2 == null){
cur.next = list1;
}
//返回记录的head；
return head.next;
}23. 合并 K 个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/description/
public ListNode mergeKLists(ListNode[] lists) {
//建立链表；
ListNode root = null;
//不断将链表元素两两合并；
for (ListNode list : lists) {
root = mergeTwoLists(root, list);
}
//返回链表；
return root;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//创建头节点和一个用于移动的节点cur；
ListNode head = new ListNode(0);
ListNode cur = head;
//边移动，边比较节点的值，并将比较结果赋值，直到有一个链表走完；
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
//判断是哪个链表走完了，把另一个链表在尾部续上；
if(list1 == null){
cur.next = list2;
}
if(list2 == null){
cur.next = list1;
}
//返回记录的head；
return head.next;
}24. 两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/
public ListNode swapPairs(ListNode head) {
//基本思路就是站在前一个节点(后续简称0节点)，向后望两个节点。
//并对这两个节点做顺序调换，之后0节点向后移动；
//创建移动的节点指针，这个节点指向head，这个就是一开始的0节点；
ListNode cur = new ListNode();
cur.next = head;
//记录头节点地址，用于返回；
ListNode root = cur;
while(true){
//没有后续节点的情况；
if(cur.next == null){
break;
}
//仍存在两个后续节点的情况；
if(cur.next.next != null){
//记录下一次需要调整顺序的节点；
ListNode temp2 = cur.next.next.next;
//调整顺序；
ListNode temp1 = cur.next;
cur.next = cur.next.next;
cur = cur.next;
cur.next = temp1;
//将节点移动到下一次调整的0节点处；
cur = cur.next;
cur.next = temp2;
}else{
//只剩一个节点的情况；
break;
}
}
//代码运行到这代表，0节点之后已经没有节点或只剩一个节点；
//返回记录的头节点；
return root.next;
}
