链表算法经典十题总结 (3)

我们了解到单链表的指针是指向下一个节点的，如果两个单链表的第一个公共节点就说明他们后面的节点都是在一起的。类似下图，由于两个链表的长度可能是不一致的，所以首先比较两个链表的长度m，n，然后用两个指针分别指向两个链表的头节点，让较长的链表的指针先走|m-n|个长度，如果他们下面的节点是一样的，就说明出现了第一个公共节点。

代码如下 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null||pHead2 == null) { return null; } int count1 = 0; ListNode p1 = pHead1; while (p1!=null){ p1 = p1.next; count1++; } int count2 = 0; ListNode p2 = pHead2; while (p2!=null){ p2 = p2.next; count2++; } int flag = count1 - count2; if (flag > 0){ while (flag>0){ pHead1 = pHead1.next; flag --; } while (pHead1!=pHead2){ pHead1 = pHead1.next; pHead2 = pHead2.next; } return pHead1; } if (flag <= 0){ while (flag<0){ pHead2 = pHead2.next; flag ++; } while (pHead1 != pHead2){ pHead2 = pHead2.next; pHead1 = pHead1.next; } return pHead1; } return null; } } 8.合并两个排序的链表 问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

算法思路

这道题比较简单，合并两个有序的链表，就可以设置两个指针进行操作即可，同时比较大小，但是也需要注意两个链表的长度进行比较。

代码如下 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode head = new ListNode(-1); ListNode cur = head; while (list1 != null && list2 != null) { if (list1.val <= list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } if (list1 != null) cur.next = list1; if (list2 != null) cur.next = list2; return head.next; } } 9.复杂的链表复制 问题描述

题目：请实现函数ComplexListNode Clone(ComplexListNode head)，复制一个复杂链表。在复杂链表中，每个结点除了有一个Next指针指向下一个结点外，还有一个Sibling指向链表中的任意结点或者NULL。

　下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。

算法思路 第一种：O(n2)的普通解法

　　第一步是复制原始链表上的每一个结点，并用Next节点链接起来；
　　第二步是设置每个结点的Sibling节点指针。
　　

第二种 ：借助辅助空间的O(n)解法

　　第一步仍然是复制原始链表上的每个结点N创建N'，然后把这些创建出来的结点用Next链接起来。同时我们把<N,N'>的配对信息放到一个哈希表中。
　　第二步还是设置复制链表上每个结点的m_pSibling。由于有了哈希表，我们可以用O(1)的时间根据S找到S'。

第三种：不借助辅助空间的O(n)解法

　　第一步仍然是根据原始链表的每个结点N创建对应的N'。（把N'链接在N的后面）