链表相关内容

基础知识

	在链表中，每个节点包含指向下一个节点的指针，这些指针把节点连接成链状结构。在创建链表时无须事先知道链表的长度。链表节点的内存分配也不是一次性地完成，而是没添加一个节点分配一次内存，可以充分利用计算机的内存资源，
所以链表节点在内存中的地址并不是连续的，查询效率比较低。和数组相比，链表更适合用来存储一个大小动态变化的数据集，如频繁的添加新元素并且不需
要考虑顺序。

基本结构

public class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}
}

哨兵节点

	哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义。在一个有哨兵节点的链表中，从第
二个节点才开始真正保存有意义的信息。

示例一，用哨兵节点简化链表插入操作

	链表的一个基本操作是在链表的尾部添加一个节点。由于通常只有一个指向单向链表头节点的指针，因此需要遍历链表中的节点直至到达链表的尾部，然
后在尾部添加一个节点。可以用如下代码实现

//没用哨兵节点的实现
public ListNode append(ListNode head, int val){ListNode newNode = new ListNode(val);//需要对头节点判空if(head == null){return newNode;}ListNode node = head;while(node.next != null){node = node.next;}node.next = newNode;return head;
}//使用哨兵节点的实现,由于创建了一个哨兵节点，所以链表无论如何都不会为空
public ListNode append(ListNode head, int val){//创建哨兵节点ListNode dumpNode = new ListNode(-1);//将哨兵节点的下一个节点指向头节点dumpNode.next  = head;ListNode newNode = new ListNode(val);ListNode node = dumpNode;while(node.next != null){node = node.next;}node.next = newNode;return dumpNode.next;
}

示例二，用哨兵节点简化链表删除操作

	链表删除节点，需要找到被删除节点的前一个节点和下一个节点，然后将前一个节点的next指向下一个节点，用如下代码实现。

//没用哨兵节点的实现
public ListNode delete(ListNode head,int val){if(head == null){return head;}if(head.val == val){return head.next;}ListNode node = head;while(node.next != null){if(node.next.val == val){node.next = node.next.next;break;}node = node.next;}return head;
}//使用哨兵节点实现，由于创建了一个哨兵节点，所以链表无论如何都不会为空
public ListNode delete(ListNode head, int val){ListNode dumpNode = new ListNode(-1);dumpNode.next = head;ListNode node = dumpNode;while(node.next != null){if(node.next.val == val){node.next = node.next.next;}node = node.next;}return dumpNode.next;
}

双指针

	链表也可以用双指针解决很多问题，一般常用两种双指针方法。一种前后双指针，即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第二个指针。前后双指针的经典应用是查找链表的倒数第k
个节点。先让第一个指针从链表头节点往后移动k-1步，然后第二个指针指向头节点，然后两个指针同时移动，当第一个指针到达尾节点时，第二个指针正好
指向倒数第k个节点。一种是快慢指针，即两个指针在链表中移动的速度不同，一般是快指针和慢指针同向移动，快指针一次移动两步，慢指针一次移动一步，在一个没有环的
链表中，如果快指针到达尾节点，则慢指针正好在中间节点。

例题解答

1、删除倒数第k个节点

题目

	如果给定一个链表，请问如何删除链表中的倒数第k个节点？假设链表中节点的总数为n，那么1<=k<=n.要求只能遍历链表一次。

分析

	定义两个指针，第一个指针p1从链表头节点开始向前移动k步，第二个指针p2再指向头节点，从第k+1步开始，p1和p2指针以相同的速度移动遍历，当p1
到达尾节点时，p2指针正好指向倒数第k+1个节点，然后修改指针指向删除第k个节点

示例代码

public static ListNode removeNthFromEnd(ListNode head,int k){ListNode dumpNode = new ListNode(-1);dumpNode.next = head;ListNode p1= head, p2= dumpNode;for(int i = 0; i < k; i ++){p1 = p1.next;}while(p1 != null){p1 = p1.next;p2 = p2.next;}p2.next = p2.next.next;return dumpNode.next;
}

2、链表中环的入口节点

题目

	如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着next指针方向进入环的第一个节点为环的入口节点。

分析

	首先需要确定链表中是否有环，可以使用快慢双指针来解决，两个指针都从头部出发，快指针一次走两步，慢指针一次走一步，如果快指针到达终点还
未和慢指针相遇，则不存在环。再需要找到环的入口节点，则可以使用前后双指针来解决,当前面已经证明链表存在环时，并返回两个指针相遇的节点，然后将第一个指针从第一步相遇的节点开始，第二个指针从链表的头节点开始，当两个指针再次相遇时，则相遇节点即为环的入口。

示例代码

public static ListNode getNodeInLoop(ListNode head){if(head == null || head.next == null){return null;}ListNode slow = head;ListNode fast = slow.next;while(slow != null && fast != null){if(slow == fast){return slow;}slow = slow.next;fast = fast.next;if(fast != null){fast = fast.next;}}return null;
}public static ListNode detectCycle(ListNode head){ListNode inLoop = getNodeInLoop(head);if(inLoop == null){return null;}ListNode node = head;while(node != inLoop){node = node.next;inLoop = inLoop.next;}return node;
}

3、两个链表的第一个重合节点

题目

	输入两个单向链表，请问如何找出它们的第一个重合节点。

分析

	还是使用双指针思想解决，可以先获取两个链表的长度，相对长的链表上进行第一个指针的移动，从链表头节点开始移动，移动个数为两个链表的长度之
差，然后开始第一个和第二个指针同时移动，第二个指针是从相对较短链表的头节点开始移动，两个指针移动速度相同，当两个指针相遇时，即为第一个重合
节点。

示例代码

public static ListNode getIntersectionNode(ListNode headA,ListNode headB){int count1 = countList(headA);int count2 = countList(headB);int delta = Math.abs(count1 - count2);ListNode longNode = count1 > count2 ? headA : headB;ListNode shortNode = count1 > count2 ? headB : headA;ListNode temp1Node = longNode;for(int i = 0; i < delta; i ++){temp1Node = temp1Node.next;}ListNode temp2Node = shortNode;while(temp1Node != temp2Node){temp1Node = temp1Node.next;temp2Node = temp2Node.next;}return temp1Node;
}public static int countList(ListNode head){int result = 0;while(head != null){head = head.next;result ++;}return result;
}

4、反转链表

题目

	定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

分析

	首先确定返回值，需要返回的时反转后链表的头节点，为了防止链表断裂，进行反转的时候最少需要知道三个节点才可以，利用数组进行排序的思想
进行交换，然后将节点指针指向交换后的节点即可。

示例代码

public static ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null){ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
}

5、链表中的数字相加

题目

	给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用户单向链表表示？链表中的每个节点表示整数十进制的一位，
并且头节点对应整数的最高位数而尾节点对应整数的个位数。

分析

	由于题中链表每个节点表示的事十进制的一位，并且是高位往低位的，并且两个链表长度可能不同，所以考虑先将链表进行翻转，再依次进行加法，再
给新链表赋值，最后再将新链表翻转即可。

示例代码

    //翻转链表方法public static ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}public static ListNode addTwoNumbers(ListNode head1,ListNode head2){head1 = reverseList(head1);head2 = reverseList(head2);ListNode reverseHead = addReversed(head1, head2);return reverseList(reverseHead);}public static ListNode addReversed(ListNode head1, ListNode head2){ListNode dumpNode = new ListNode(-1);ListNode sumNode = dumpNode;int carry = 0;while(head1 != null || head2 != null){int sum = (head1 == null ? 0 : head1.val) + (head2 == null ? 0 : head2.val) + carry;carry = sum >=10 ? 1: 0;sum = sum >= 10 ? sum - 10 : sum;ListNode newNode = new ListNode(sum);sumNode.next = newNode;sumNode = sumNode.next;head1 = head1 == null ? null : head1.next;head2 = head2 == null ? null : head2.next;}if(carry > 0){sumNode.next = new ListNode(carry);}return dumpNode.next;}

6、重排链表

题目

	给定一个链表，链表中节点的顺序是L0->L1->L2->...->Ln-1->Ln,请问如何重排链表使节点的顺序变成L0->Ln->L1->Ln-1->l2->Ln-2->...?。

分析

	首先需要解决的问题是将链表分成两半，找到中间节点可以使用快慢双指针解法，然后将链表分成两个链表，然后将后部分链表进行翻转，然后遍历两个
链表进行指针变化即可。

示例代码

public static void reorderList(ListNode head){ListNode dumpNode = new ListNode(-1);dumpNode.next = head;ListNode fast = dumpNode;ListNode slow = dumpNode;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next;if(fast.next != null){fast = fast.next;}}//中间节点ListNode temp = slow.next;slow.next = null;link(head,reverseList(temp),dumpNode);
}
public static ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}
public static void link(ListNode node1, ListNode node2, ListNode head){ListNode pre = head;while(node1 != null && node2 != null){ListNode temp = node1.next;pre.next = node1;node1.next = node2;pre = node2;node1 = temp;node2 = node2.next;}if(node1 != null){pre.next = node1;}
}

7、回文链表

题目

	如何判断一个链表是不是回文？要求解法的时间复杂度是O(n)，并且不得使用超过O(1)的辅助空间。如果一个链表使回文，那么链表的节点序列从前往后
看和从后往前看是相同的。

分析

	将链表分成前后两段，然后将后段链表进行翻转，再遍历比较即可解决

示例代码

public static boolean isPalindrome(ListNode head){if(head == null || head.next == null){return true;}ListNode slow = head;ListNode fast = head.next;while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next;if(fast.next != null){fast = fast.next;}}ListNode temp = slow.next;if(fast.next != null){temp = slow.next.next;}slow.next = null;return equals(temp,reverseList(head));
}
public static ListNode reverseList(ListNode head){ListNode pre = null;ListNode cur = head;while(cur != null){ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;
}public static boolean equals(ListNode node1, ListNode node2){while(node1 != null && node2 != null){if(node1.val != node2.val){return false;}node1 = node1.next;node2 = node2.next;}return node1 == null && node2 == null;
}

双向链表和循环链表

	双向链表在单向链表的节点的基础上增加了一个指向前一个节点的指针，这样一来，即可以从头节点开始从前往后遍历到尾节点，可以了从尾节点开始从
后往前遍历到头节点。因为增加了一个指针，所以添加、删除节点操作会复杂一些。

8、展平多级双向链表

题目

	在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向
子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。

分析

	首先要清楚展平规则，以规则是一个节点的子链表展平之后将插入该节点和它的下一个节点之间为例，由于子链表中的节点也可能有子链表，因此这里的
链表是一个递归结构。

示例代码

public static Node flatten(Node head){flattenGetTail(head);return head;
}
public static Node flattenGetTail(Node head){Node node = head;Node tail = null;while(node != null){Node next = node.next;//判断子链表是否为空if(node.child != null){//获取子链表Node child = node.child;//多子链表进行展平Node childTail = flattenGetTail(child);//展平之后节点的子链表为空node.child = null;//将节点的下一个指针指向子链表的头节点node.next = child;//将子链表的头节点的前一个指针指向node节点child.prev = node;// 将子链表的尾节点的下一个指针指向 node的下一个节点childTail.next = next;if(next != null){//如果下一个节点不是空，则将下一个节点的前一个指针指向子链表的尾节点next.prev = childTail;}//将子链表的尾节点赋值给原来的尾节点tail = childTail;}else{//如果没有子链表，则将当前节点赋值给尾节点tail = node;}//将下一个节点赋值给当前节点，进行链表遍历node = next;}return tail;
}

9、排序的循环链表

题目

	在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。

分析

	新插入的节点值可能会有三种情况：1、比现有链表中最大值还大，则将新节点插入到最大值与最小值之间；2、比现有链表中最小值还小，则将新节点
插入到最大值与最小值之间；3、在链表中找到比插入新节点值大和小的相邻两个节点，将新节点插入。再就是链表只有一个节点和两个节点的情况，如果只有一个节点怎么插入都行，如果是两个节点则需要比较节点的值和新节点的值进行插入。

示例代码

public static Node insert(Node head,int insertVal){Node node = new Node(insertVal);if(head == null){head = node;head.next = head;}else if(head.next == head){head.next = node;node.next = head;}else{insertCore(head,node);}return head;
}
public static void insertCore(Node head,Node node){Node cur = head;Node next = head.next;Node biggest = head;//未找到Node属于相邻两个节点之间时，去遍历链表获取链表最大值的节点while(!(cur.val <= node.val && next.val >= node.val) && next != head){cur = next;next = next.next;if(cur.val >= biggest.val){biggest = cur;}}//正常情况下，找到大于node值的和小于node值的两个相邻节点，将node插入进去if(cur.val <= node.val && next.val >= node.val){cur.next = node;node.next = next;}else{//特殊情况，将node插入到最大节点和最小节点之间node.next = biggest.next;biggest.next = node;}
}

总结

	由于链表再内存中地址不连续，所以访问时需要从头开始逐个遍历。可以哨兵节点简化代码判断逻辑。合理利用双指针前后移动和双指针快慢指针能解决
一些问题。双向链表和循环链表操作时需要特别注意，避免产生死循环。