【算法训练营Day04】链表part2

两两交换链表中的节点

题目链接：24. 两两交换链表中的节点

算法逻辑：

• 添加一个虚拟头节点
• 初始化一个交换指针，代表每次交换指针的后两个节点，该指针从虚拟头节点开始移动
• 接下来就是交换步骤
  • 先将交换指针的后面第一个节点（简称后1节点）以及交换指针的后3节点存起来
  • 将交换指针的后2节点与交换指针节点进行缝合
  • 将存起来的后1节点与后2节点进行缝合
  • 在将存起来的后3节点与后1节点进行缝合
• 如此交换直到交换指针节点为null，或者后1节点为null，或者后2节点为null，因为必须要有两个节点才能交换

/*** 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 || head.next == null) return head;ListNode virtualHead = new ListNode(-1,head);ListNode exchangePointer = virtualHead;while(exchangePointer != null && exchangePointer.next != null && exchangePointer.next.next != null) {ListNode temp1 = exchangePointer.next;ListNode temp3 = temp1.next.next;exchangePointer.next = exchangePointer.next.next;exchangePointer.next.next = temp1;exchangePointer.next.next.next = temp3;exchangePointer = exchangePointer.next.next;}return virtualHead.next;}
}

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

题目链接：19. 删除链表的倒数第 N 个结点

逻辑思路：
这道题既然是删除倒数的第n个节点，那么我们可以将链表反转，然后再删除第n个，最后再把链表反转回去即可。我们前几天的训练营中做过移除链表元素、翻转链表等算法题，所以这里直接把相关方法移植过来即可。

代码：

/*** 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 reverseList = reverseList(head);ListNode deleteList = deleteAtCount(reverseList,n);return reverseList(deleteList);}public ListNode reverseList(ListNode head) {ListNode reverseResultVirtualHead = new ListNode();ListNode pointer = head;while(pointer != null) {ListNode currentNode = new ListNode(pointer.val,null);currentNode.next = reverseResultVirtualHead.next;reverseResultVirtualHead.next = currentNode;pointer = pointer.next;}return reverseResultVirtualHead.next;}public ListNode deleteAtCount(ListNode head,int count) {ListNode virtualHead = new ListNode(-1,head);ListNode pointer = virtualHead;while(count > 0 && pointer.next != null) {if(count == 1) {pointer.next = pointer.next.next;}count -= 1;pointer = pointer.next;}return virtualHead.next;}
}

链表相交

题目链接：面试题 02.07. 链表相交

算法逻辑：
读完题目之后可以发现一个特点那就是若链表相交，那么必有公共后缀！我们若想找到两个链表的公共后缀那么第一想法肯定就是反向遍历。但是这是一个单向链表，直接反向遍历无法实现，这个时候我们就可以借助于栈结构来完成公共后缀的比对。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null) return null;ListNode pointerA = headA;ListNode pointerB = headB;Stack<ListNode> a = new Stack<ListNode>();Stack<ListNode> b = new Stack<ListNode>();while(pointerA != null) {a.push(pointerA);pointerA = pointerA.next;}while(pointerB != null) {b.push(pointerB);pointerB = pointerB.next;}ListNode nodeA = a.pop();ListNode nodeB = b.pop();ListNode result = null;while(nodeA == nodeB) {result = nodeA;if (a.empty() || b.empty()) break;nodeA = a.pop();nodeB = b.pop();}return result;}
}

环形链表 II

题目链接： 142. 环形链表 II

解题思路：

判断是否成环，换一句话说也就是在遍历链表的时候看是否有重复的节点，第一个重复的节点就是成环的起点。我们可以利用set数据结构，每遍历到一个新节点就看set中是否有相同节点，如果没有就添加到set中，如果有则说明该节点就是成环节点。遍历完了都没有重复节点，则说明不成环。

代码：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> nodeSet = new HashSet();ListNode pointer = head;while(pointer != null) {if(nodeSet.contains(pointer)) return pointer;nodeSet.add(pointer);pointer = pointer.next;}return null;}
}

链表总结

链表的关键点就在于：

• 增加、删除的时候可以引入虚拟头节点，让逻辑更加统一，不用单独考虑一些边界情况
• 如果是遍历等不会修改链表结构的操作则无需引入虚拟头节点
• 增加删除的重点就在于增加、删除元素的前后链要是可见的，才能完成相关的节点缝合工作。这就需要我们引入一些中间变量来存储这些前后链.