链表常见题|删除链表、合并链表、环形链表、相交链表、反转链表、回文链表

2.两数相加

/*** 两数相加*/
public class $2 {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = new ListNode(-1);ListNode cur = head;int carry = 0;while (l1 != null || l2 != null) {int x = l1 == null ? 0 : l1.val;int y = l2 == null ? 0 : l2.val;int sum = x + y + carry; //计算需要考虑进位问题carry = sum / 10;sum = sum % 10;cur.next = new ListNode(sum);if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}cur = cur.next;}if (carry != 0) {cur.next = new ListNode(carry);}return head.next;}
}

19.删除链表的倒数第 N 个结点

删除链表的倒数第 n 个节点

特殊值考虑：head==null; head.next==null&&n==1

1.fast先走n步

2.若n大于链表长度时，删除头结点

3.fast和slow同时走，直到fast.next==null

4.删除，slow所指向的节点即为被删除节点的前序节点

/*** 删除链表的倒数第 n 个节点* 特殊值考虑：head==null; head.next==null&&n==1* 1.fast先走n步* 2.若n大于链表长度时，删除头结点* 3.fast和slow同时走，直到fast.next==null* 4.删除，slow所指向的节点即为被删除节点的前序节点*/
public class $19 {public ListNode removeNthFromEnd(ListNode head, int n) {if (head == null) {return null;}if (head.next == null && n == 1) {  //保证n是有效的，说明n只可能为1？return null;}ListNode fast = head;ListNode slow = head;for (int i = 0; i < n; i++) {fast = fast.next;}if (fast == null) { //要注意链表长度 == n时，会fast会越界return head.next;}while (fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return head;}public ListNode removeNthFromEnd2(ListNode head, int n) {if (head == null) {return null;}//([1], 1)if (head.next == null && n == 1) {return null;}ListNode fast = head;ListNode slow = head;//1.fast先走n步for (int i = 0; i < n; i++) {fast = fast.next;}//2.若n大于链表长度时，删除头结点if (fast == null) {return head.next;}//3.fast和slow同时走while (fast.next != null) {fast = fast.next;slow = slow.next;}//4.删除//slow所指向的节点即为被删除节点的前序节点slow.next = slow.next.next;return head;}
}

21.合并两个有序链表

/*
合并两个有序链表*/
public class $21 {public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);ListNode cur = head;while (list1 != null && list2 != null) {if (list1.val < list2.val) {cur.next = new ListNode(list1.val);list1 = list1.next;} else {cur.next = new ListNode(list2.val);list2 = list2.next;}cur = cur.next;}if (list1 != null) {cur.next = list1;}if (list2 != null) {cur.next = list2;}return head.next;}
}

141.环形链表

• 使用快慢指针，若两指针重合，说明有环
• 注：循环条件的顺序
• 判断指针相等，要在先前进之后

/*** 使用快慢指针，若两指针重合，说明有环* 注：循环条件的顺序* 判断指针相等，要在先前进之后*/
public class $141 {public static boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {return true;}}return false;}
}

142.环形链表 II

当快慢指针重合的时候，head到入环结点的距离等于重合结点到入环节点的距离

/*** 当快慢指针重合的时候，head到入环结点的距离等于重合结点到入环节点的距离*/
public class $142 {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {break;}}//不带环的情况// fast == slow 不能证明链表带环，比如链表只有一个节点if (fast == null || fast.next == null) {return null;}//cur 和 fast 同时走相同的步数//循环条件：cur ！= fast，若一开始 cur = fast说明两者已在入环结点ListNode cur = head;while (cur != fast) {cur = cur.next;fast = fast.next;}return cur;}
}

160.相交链表

法一：

1.让较长的链表的先走差值步

2.两个链表同时走

3.若相等，则有相交点 *

法二：让两个链表从同距离末尾同等距离的位置开始遍历，其中一个位置是较短链表的头结点位置。

1.指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历

2.如果 pA 到了末尾，则 pA = headB 继续遍历

3.如果 pB 到了末尾，则 pB = headA 继续遍历

4.比较长的链表指针指向较短链表head时，长度差就消除了

/*** 法一：* 1.让较长的链表的先走差值步* 2.两个链表同时走* 3.若相等，则有相交点*/
public class $160 {//法一：public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//1.两个链表的长度int lenA = size(headA);int lenB = size(headB);int k = 0;int flg = 1;//2.长的链表先走长度差步if (lenA>lenB) {k = lenA - lenB;} else {k = lenB - lenA;flg = 0;}if (flg == 1) {for (int i = 0; i < k; i++) {headA = headA.next;}} else {for (int i = 0; i < k; i++) {headB = headB.next;}}//3.两个链表同时走while (headA != null && headB != null) {if (headB == headA) {return headB;}headA = headA.next;headB = headB.next;}return null;}private static int size(ListNode head) {int len = 0;for (ListNode node = head; node != null; node = node.next) {len++;}return len;}
}

/**** 法二：让两个链表从同距离末尾同等距离的位置开始遍历，其中一个位置是较短链表的头结点位置。* 1.指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历* 2.如果 pA 到了末尾，则 pA = headB 继续遍历* 3.如果 pB 到了末尾，则 pB = headA 继续遍历* 4.比较长的链表指针指向较短链表head时，长度差就消除了*/
public class $160 {//法二public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

206.反转链表

/*** 反转链表*/
public class $206 {public ListNode reverseList2(ListNode head) {if (head == null) {return null;}ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}
}

234.回文链表

1.找到链表的中间节点

2.中间节点之后的链表反转

3.比较

/*** 链表的回文* 1.找到链表的中间节点* 2.中间节点之后的链表反转* 3.比较*/
public class $234 {public boolean isPalindrome2(ListNode head) {//1.找到链表的中间节点ListNode mid = getMidNode(head);//2.反转链表ListNode rev = revList(mid.next);//3.比较ListNode l1 = head;ListNode l2 = rev;while (l1 != null && l2 != null) {if (l1.val != l2.val) {return false;}l1 = l1.next;l2 = l2.next;}return true;}private ListNode getMidNode(ListNode head) {ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) {fast = fast.next.next;slow = slow.next;}return slow;}private ListNode revList(ListNode head) {ListNode prev = null;ListNode cur = head;while (cur != null) {ListNode next = cur.next;cur.next = prev;prev = cur;cur = next;}return prev;}
}