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

　　第二步设置复制出来的结点的Sibling。（把N'的Sibling指向N的Sibling）
　

　　第三步把这个长链表拆分成两个链表：把奇数位置的结点用Next链接起来就是原始链表，偶数数值的则是复制链表。

代码如下 public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) { return null; } RandomListNode currentNode = pHead; //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面； while(currentNode != null){ RandomListNode cloneNode = new RandomListNode(currentNode.label); RandomListNode nextNode = currentNode.next; currentNode.next = cloneNode; cloneNode.next = nextNode; currentNode = nextNode; } currentNode = pHead; //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next; while(currentNode != null) { currentNode.next.random = currentNode.random==null?null:currentNode.random.next; currentNode = currentNode.next.next; } //3、拆分链表，将链表拆分为原链表和复制后的链表 currentNode = pHead; RandomListNode pCloneHead = pHead.next; while(currentNode != null) { RandomListNode cloneNode = currentNode.next; currentNode.next = cloneNode.next; cloneNode.next = cloneNode.next==null?null:cloneNode.next.next; currentNode = currentNode.next; } return pCloneHead; } } 10.反转链表 问题描述

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。如图：

算法思路

为了正确地反转一个链表，需要调整链表中指针的方向。为了将复杂的过程说清楚，这里借助于下面的这张图片。

上面的图中所示的链表中，h、i和j是3个相邻的结点。假设经过若干操作，我们已经把h结点之前的指针调整完毕，这个结点的m_pNext都指向前面的一个结点。接下来我们把i的m_pNext指向h，此时结构如上图所示。

从上图注意到，由于结点i的m_pNext都指向了它的前一个结点，导致我们无法在链表中遍历到结点j。为了避免链表在i处断裂，我们需要在调整结点i的m_pNext之前，把结点j保存下来。

即在调整结点i的m_pNext指针时，除了需要知道结点i本身之外，还需要i的前一个结点h，因为我们需要把结点i的m_pNext指向结点h。同时，还需要实现保存i的一个结点j，以防止链表断开。故我们需要定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。故反转结束后，新链表的头的结点就是原来链表的尾部结点。尾部结点为m_pNext为null的结点。

代码如下 public class ReverseList_16 { public ListNode ReverseList(ListNode head) { if (head == null || head.nextNode == null) { return head; } ListNode next = head.nextNode; head.nextNode = null; ListNode newHead = ReverseList(next); next.nextNode = head; return newHead; } public ListNode ReverseList1(ListNode head) { ListNode newList = new ListNode(-1); while (head != null) { ListNode next = head.nextNode; head.nextNode = newList.nextNode; newList.nextNode = head; head = next; } return newList.nextNode; } }

参考：

https://blog.csdn.net/u010983881/article/details/78896293

https://blog.csdn.net/inspiredbh/article/details/54915091

https://www.jianshu.com/p/092d14d13216

https://www.cnblogs.com/bakari/p/4013812.html

https://blog.csdn.net/u013132035/article/details/80589657