算法题（链表）

一、题目

1、两两交换链表中的节点（LC 24）

2、删除链表的倒数第N个节点（LC 19）

3、两数相加（LC 2）

二、题解

1、两两交换链表中的节点（LC 24）

（1）分析

可以使用迭代法解决。遍历链表时，对于每一组需要交换的节点，同时操作前驱节点、当前节点、后继节点三者的指针指向，才能完成交换，避免链表断裂。具体来说：先让当前节点指向后继节点的下一个节点，再让后继节点回指当前节点，最后让前驱节点指向新的头部节点，完成一组交换。

需要创建哨兵节点 dummy，用来固定新链表的头节点位置 —— 因为两两交换会直接改变原链表的头节点，原 head 指针会指向第二个节点，无法作为结果返回。迭代过程遍历链表一次，每个节点仅访问一次。时间复杂度为 O (n)，空间复杂度为 O (1)。

（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 swapPairs(ListNode head) { if(head == null)return null; ListNode dummy = new ListNode(0); //哨兵节点，方便返回结果 dummy.next = head; ListNode curr = head; //当前节点 ListNode pre = dummy; //当前节点前一个节点 while(curr != null && curr.next != null){ ListNode next = curr.next; //当前节点后一个节点 curr.next = next.next; // next.next = curr; //改变指针朝向，交换位置 pre.next = next; // pre = curr; //更新前驱节点 curr = curr.next; //更新当前节点。已经后继结点交换位置了，只需要再向后移动一次 } return dummy.next; } }

2、删除链表的倒数第N个节点（LC 19）

（1）分析

采用快慢双指针解决。首先创建哨兵节点作为整个链表的虚拟头节点，让它指向原头节点，再定义快指针 start 和慢指针 end 都指向哨兵节点。

第一步先让快指针单独向前移动 n 步，使快慢指针之间保持固定的 n 个节点间距；第二步让快慢指针同步向后移动，直到快指针到达链表末尾。此时慢指针恰好指向待删除节点的前驱节点，直接修改前驱节点的指针指向 end.next = end.next.next，即可跳过并删除目标节点。

由于待删除节点可能是原链表的头节点，head 指针会失效，因此最终必须返回哨兵节点的后继节点，不能直接返回 head。时间复杂度为 O (n)，空间复杂度为 O (1)。

（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 removeNthFromEnd(ListNode head, int n) { ListNode pre = new ListNode(0); pre.next = head; ListNode start = pre, end = pre; while(n>0){ start = start.next; n--; } while(start.next != null){ start = start.next; end = end.next; } end.next = end.next.next; return pre.next; } }

3、两数相加（LC 2）

（1）分析

链表从头部到尾部对应数字的低位到高位。遍历两个链表时，自动对齐位数：若一个链表已遍历完毕，则对应位用 0 补充。每一轮计算当前位的和（两个节点值 + 上一轮进位），用取余 sum%10 得到当前位的结果存入新节点，用取整 sum/10 更新进位值。循环遍历直到两个链表都为空。

使用哨兵节点指向新链表的头节点，避免空指针判断，最后直接返回哨兵节点的后继节点作为结果链表头。时间复杂度为 O (max (n,m))，空间复杂度为 O (max (n,m)。

（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 addTwoNumbers(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode curr = pre; int flag = 0; while(l1!=null || l2!=null){ int x = l1 == null ? 0 : l1.val; int y = l2 == null ? 0 : l2.val; int sum = x + y + flag; flag = sum / 10 ; sum = sum % 10; ListNode node = new ListNode(sum); curr.next = node; curr = curr.next; if(l1 != null)l1 = l1.next; if(l2 != null)l2 = l2.next; } if(flag == 1){ ListNode node = new ListNode(1); curr.next = node; } return pre.next; } }