算法题（链表）

一、题目1、两两交换链表中的节点LC 242、删除链表的倒数第N个节点LC 193、两数相加LC 2二、题解1、两两交换链表中的节点LC 241分析可以使用迭代法解决。遍历链表时对于每一组需要交换的节点同时操作前驱节点、当前节点、后继节点三者的指针指向才能完成交换避免链表断裂。具体来说先让当前节点指向后继节点的下一个节点再让后继节点回指当前节点最后让前驱节点指向新的头部节点完成一组交换。需要创建哨兵节点 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 191分析采用快慢双指针解决。首先创建哨兵节点作为整个链表的虚拟头节点让它指向原头节点再定义快指针 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(n0){ start start.next; n--; } while(start.next ! null){ start start.next; end end.next; } end.next end.next.next; return pre.next; } }3、两数相加LC 21分析链表从头部到尾部对应数字的低位到高位。遍历两个链表时自动对齐位数若一个链表已遍历完毕则对应位用 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; } }