链表篇
常用链表定义：
public class ListNode
{
int val;
ListNode next;
ListNode(int x)
{
val=x;
}
}
单链表的创建与遍历
public class LinkList {
public Node head;
public Node current;
//方法：向链表中添加数据
public void add(int data) {
//判断链表为空的时候
if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
head = new Node(data);
current = head;
} else {
//创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
current.next = new Node(data);
//把链表的当前索引向后移动一位
current = current.next; //此步操作完成之后，current结点指向新添加的那个结点
}
}
public void print(Node node) {
if (node == null) {
return;
}
current = node;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
class Node {
//注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
int val; //数据域
Node next;//指针域
public Node(int val) {
this.val= val;
}
}
}
复杂链表的复制
问题
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回这个链表的复制。
问题链接
参考地址
http://wiki.jikexueyuan.com/project/for-offer/question-twenty-six.html
代码实现
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
//参考链接：http://wiki.jikexueyuan.com/project/for-offer/question-two.html
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null)
return pHead;
//为每一个结点创建一个副本结点
RandomListNode newHead=pHead;
while(newHead!=null){
RandomListNode node=new RandomListNode(newHead.label);
node.next=newHead.next;
newHead.next=node;
newHead=newHead.next.next;
}
//处理random结点
RandomListNode newHead2=pHead;
while(newHead2!=null){
//注意这里，空指针异常
RandomListNode next=newHead2.next;
RandomListNode random=newHead2.random;
if(random!=null)
next.random=random.next;
newHead2=next.next;
}
//拆分原链表和副本链表
RandomListNode cloneNode=pHead.next;//副本链表的头结点
RandomListNode newHead3=pHead;//原链表的遍历指针
while(newHead3!=null){
RandomListNode next=newHead3.next;//副本链表
newHead3.next=next.next;
newHead3=newHead3.next;
if(newHead3!=null)
next.next=newHead3.next;
}
return cloneNode;
}
}
二叉搜索树转为有序的双向链表
问题
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
代码实现：
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode phead;
TreeNode realhead;
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
return pRootOfTree;
ConvertSub(pRootOfTree);
return realhead;
}
//中序遍历
public void ConvertSub(TreeNode root){
if(root==null)
return ;
ConvertSub(root.left);
if(phead==null){
phead=root;
realhead=root;
}
else{
phead.right=root;
root.left=phead;
phead=root;
}
ConvertSub(root.right);
}
}
以下内容为转载 原文：http://wuchong.me/blog/2014/03/25/interview-link-questions/
在O(1)时间删除链表节点
题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]
分析：要想在O（1）时间搞定，绝对不能用遍历。，本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。
特殊情况 1.如果要删除的节点没有下一个节点： 则要找到上一个节点，并且将next设置为空，这个时候只能用遍历
2.如果当前链表就一个节点 由于java中没有指向指针的指针，所以用返回null。
代码实现：
//O(1)时间删除链表节点，从无头单链表中删除节点
/**
* 在时间复杂度为O(1)的情况下删除链表的节点。<br/>
* 不过有个前提是要删除的这个节点必须在链表中包含，不然不会报错也不会改变原先的链表
* */
public Node delete(Node head, Node node) {
// 检查空
if (node == null) {
throw new RuntimeException();
}
Node next = node.next;
if (next != null) {
// 有下一个节点的情况：复制覆盖
node.value = next.value;
node.next = next.next;
// 没有下一个节点的情况
} else {
Node previous = null;
Node current = head;
while (current != null) {
if (current == node) {
// 前一个为空，要删除的节点即是第一个头结点
if (previous == null) {
head = null;
} else {
// 前一个不为空，则将next置为null即可
previous.next = null;
}
}
previous = current;
current = current.next;
}
}
return head;
}
平均时间复杂度[(n-1)*O(1)+O(n)]/n，仍然为O(1)
2. 单链表的转置
题目描述：
给一个单向链表，把它从头到尾反转过来。比如： a -> b -> c ->d 反过来就是 d -> c -> b -> a 。
分析：
链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。
非递归
//单链表的转置,非递归
public Node reverse(Node current) {
//初始化
Node previousNode = null;
Node nextNode = null;
while (current != null) {
//保留下一个结点
nextNode = current.next;
//将当前结点的下一个指针指向previous结点，即翻转
current.next = previousNode;
//移动指针
previousNode = current;
current = nextNode;
}
return previousNode;
}
递归方法
public Node reverse(Node current)
{
if (current == null || current.next == null) return current;
Node nextNode = current.next;
Node reverseRest = reverse(nextNode);
nextNode.next = current;
current.next = null; //防止循环链表
return reverseRest;
}
递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个node的next 值 (代码倒数第二句)。 在上面的代码中， reverseRest 的值没有改变，为该链表的最后一个node，所以，反转后，我们可以得到新链表的head。
3. 求链表倒数第k个节点
题目描述：
输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第0个节点为链表的尾指针。
分析：
设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。
代码如下：
public ListNode FindKthToTail(ListNode head,int k) {
if (k <= 0 || head == null) {
return null;
}
int index = 0;
ListNode targetNode = head;
ListNode node = head;
int len= 0;//统计长度
while (node != null) {
if (index >= k) {
targetNode = targetNode.next;
}
index++;
node = node.next;
len++;
}
// 是否k的值大于了链表的长度
if (len< k) {
return null;
}
return targetNode;
}
4. 求链表的中间节点
题目描述：
求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。
分析：
此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。
代码如下：
/**
* 此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步
* 前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点，即第（n/2+1）个结点。注意链表为空，链表结点个数为1和2的情况。时间复杂度O（n ）
*/
public Node getMiddleNode(Node head) {
if (head == null || head.next == null) {
return head;
}
Node q = head; // p---q
Node p = head;
// 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步
while (q.next != null) {
q = q.next;
p = p.next;
if (q.next != null) {
q = q.next;
}
}
return p;
}
5. 判断单链表是否存在环
题目描述：
输入一个单向链表，判断链表是否有环？
分析：
通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇，时间复杂度为O (n)。
代码实现：
public boolean hasCycle(Node head) {
Node fast = head; // 快指针每次前进两步
Node slow = head; // 慢指针每次前进一步
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { // 相遇，存在环
return true;
}
}
return false;
}
6. 找到环的入口点
题目描述：
输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
方案1
解题思路：
由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。
为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：
p1走的路径： a+b ＝ n； p2走的路径： a+b+kL = 2n； p2 比 p1 多走了k圈环路，总路程是p1的2倍
根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。
显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。
代码如下：
//找到环的入口点
Node* findLoopPort(Node *head)
{
//如果head为空，或者为单结点，则不存在环
if(head == NULL || head->next == NULL) return NULL;
Node *slow,*fast;
slow = fast = head;
//先判断是否存在环
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
break;
}
if(fast != slow) return NULL; //不存在环
fast = head; //快指针从头开始走，步长变为1
while(fast != slow) //两者相遇即为入口点
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
方案二，先求环的长度
解题思路：
这里我们需要先获取环的长度length。拿到环的长度length之后，需要用到两个指针变量first和second，先让second指针走length步；然后让first指针和second指针同时各走一步，当两个指针相遇时，相遇时的结点就是环的起始点。
注：为了找到环的起始点，我们需要先获取环的长度，而为了获取环的长度，我们需要先判断是否有环。所以这里面其实是用到了三个方法。
代码实现
//方法：判断单链表是否有环。返回的结点是相遇的那个结点
public Node hasCycle(Node head) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
while (second != null) {
first = first.next;
second = second.next.next;
if (first == second) { //一旦两个指针相遇，说明链表是有环的
return first; //将相遇的那个结点进行返回
}
}
return null;
}
//方法：有环链表中，获取环的长度。参数node代表的是相遇的那个结点
public int getCycleLength(Node node) {
if (head == null) {
return 0;
}
Node current = node;
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == node) { //当current结点走到原点的时候
return length;
}
}
return length;
}
//方法：获取环的起始点。参数length表示环的长度
public Node getCycleStart(Node head, int cycleLength) {
if (head == null) {
return null;
}
Node first = head;
Node second = head;
//先让second指针走length步
for (int i = 0; i < cycleLength; i++) {
second = second.next;
}
//然后让first指针和second指针同时各走一步
while (first != null && second != null) {
first = first.next;
second = second.next;
if (first == second) { //如果两个指针相遇了，说明这个结点就是环的起始点
return first;
}
}
return null;
}
7. 编程判断两个链表是否相交
题目描述：
给出两个单向链表的头指针（如下图所示），
比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。
代码实现：
// 判断两个单链表是否相交
/**
* 如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。 也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。
* 先遍历第一个链表，记住最后一个节点，然后遍历第二个链表， 到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，
* 否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址， 空间复杂度为O(1)
*/
public static boolean isIntersect(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return false;
}
Node h1= head1;
// 找到链表1的最后一个节点
while (h1.next != null) {
h1= h1.next;
}
Node h2 = head2;
// 找到链表2的最后一个节点
while (h2 .next != null) {
h2 = h2 .next;
}
return h1== h2 ;
}
8. 扩展：链表有环，如何判断相交
题目描述：
上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?
分析：
如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上
判断一个链表环上的一点，是否在另一个链表上
因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。
代码实现：
//判断两个带环链表是否相交 bool isIntersectWithLoop(Node h1,Node h2) { Node circleNode1,circleNode2; if(!hasCircle(h1,circleNode1)) //判断链表带不带环，并保存环内节点 return false; //不带环，异常退出 if(!hasCircle(h2,circleNode2)) return false;
Node *temp = circleNode2->next;
while(temp != circleNode2)
{
if(temp == circleNode1)
return true;
temp = temp->next;
}
return false;
}
9. 两链表相交的第一个公共节点
题目描述：
如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？
分析：
采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 - L1个节点，然后再同时向后移动p1 , p2，直到 p1 = p2。相遇的点就是相交的第一个节点。
代码实现：
//求两链表相交的第一个公共节点
Node* findIntersectNode(Node *h1,Node *h2)
{
int len1 = listLength(h1); //求链表长度
int len2 = listLength(h2);
//对齐两个链表
if(len1 > len2)
{
for(int i=0;i<len1-len2;i++)
h1=h1->next;
}
else
{
for(int i=0;i<len2-len1;i++)
h2=h2->next;
}
while(h1 != NULL)
{
if(h1 == h2)
return h1;
h1 = h1->next;
h2 = h2->next;
}
return NULL;
}
合并两个有序的单链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
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 newlist=new ListNode(0);
ListNode listhead1=list1;
ListNode listhead2=list2;
if(list1==null)
return list2;
if(list2==null)
return list1;
ListNode result=newlist;
while(listhead1!=null&&listhead2!=null){
if(listhead1.val<=listhead2.val){
newlist.next=new ListNode(listhead1.val);
newlist=newlist.next;
listhead1=listhead1.next;
}
else{
newlist.next=new ListNode(listhead2.val);
newlist=newlist.next;
listhead2=listhead2.next;
}
}
while(listhead1!=null){
newlist.next=new ListNode(listhead1.val);
listhead1=listhead1.next;
}
while(listhead2!=null){
newlist.next= new ListNode(listhead2.val);
listhead2=listhead2.next;
}
return result.next;
}
}
链表的展平
问题描述：
从一个标准的双向链表开始。设想每个元素除了next和previous指针之外，还有一个child指针，这个指针可能会指向一个单独的双向链表，也可能为空。这样就产生了一个多层的数据结构。
将这个链表展平，以使得所有节点都出现在同一层的双向链表上。给定第一层链表的head和tail。每个节点定义如下：
public class Node{
Node next;
Node prev;
Node child;
int value;
}
问题分析：
从第一层开始遍历，每次遇到子节点的结点时，将这个子节点附加到第一层的结尾，并更新尾指针。
Start at the beginning of the first level
While you are not at the end of the first level
If the current node has a child
Append the child to the end of the first level
Update the tail pointer
Advance to next node
代码实现：
public Node tail;//尾指针已给出
public void flattenList(Node head){
Node curNode=head;
while(curNode!=null){
if(curNode.child!=null){
append(curNode.child,tail);
}
curNode = curNode.next;
}
}
public append(Node child){
Node curNode;
tail.next=child;
child.prev=tail;
curNode=child;
//移动尾指针
while(curNode.next!=null){
curNode=curNode.next;
}
tail=curNode;//更新尾指针。
}
取消链表展平
代码实现：
public void unflattenList(Node start,Node tail){
Node curNode;
exploreAndSeparate(start);
curNode=start;
while(curNode.next!=null){
curNode=curNode.next;
}
tail=curNode;
}
public void exploreAndSeparate(Node childListStart){
Node curNode;
while(curNode){
if(curNode.child!=null){
curNode.child.prev.next=null;
curNode.child.prev=null;
}
exploreAndSeparate(curNode.child);
}
curNode=curNode.next;
}
删除链表中重复的结点
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 链接 https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
代码实现
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead==null||pHead.next==null)
return pHead;
pHead = deleteSub(pHead);//处理以重复元素开头的元素
if(pHead==null||pHead.next==null)
return pHead;
ListNode pre=pHead;
ListNode cur=pre.next;
if(cur==null)
return pHead;
ListNode next=cur.next;
while(next!=null){
ListNode temp=null;
if(cur.val==next.val){
temp=deleteSub(cur);
if(temp==null){//若处理重复元素后，返回为空
pre.next=null;//更新指针，使其下一个结点为空
return pHead;
}
pre.next=temp;
pre=pre.next;
cur=pre.next;
if(cur==null)
return pHead;
next=cur.next;
}
else{
pre=pre.next;
cur=pre.next;
if(cur==null)
return pHead;
next=cur.next;
}
}
return pHead;
}
public ListNode deleteSub(ListNode pHead){//用于删除连续的重复元素，并返回下一个不重复的元素
if(pHead==null||pHead.next==null)
return pHead;
while(pHead.next.val==pHead.val){//处理111223344的情况
while(pHead.next.val==pHead.val){
pHead=pHead.next;
if(pHead.next==null)
return null;
}
pHead=pHead.next;
if(pHead.next==null)
return pHead;
}
return pHead;
}
}
二叉树的下一个结点
题目描述:
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
分析：
三种情况：
- 树为空，则返回null
- 当前结点有右子树，则返回右子树的最左结点
- 当前结点没有右子树，则遍历其父节点，当当前结点的父节点的左子树就是当前结点时，返回其父节点，就是最开始所求结点按中序遍历的下一个结点
针对第三种情况的分析
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null)
return null;
if(pNode.right!=null){//右子树不为空
pNode=pNode.right;
while(pNode.left!=null)
pNode=pNode.left;
return pNode;
}
//pNode.next表示的是PNode的父节点。
while(pNode.next!=null){//没右子树，则找第一个当前节点是父节点左孩子的节点
if(pNode.next.left==pNode)
return pNode.next;
pNode=pNode.next;
}
return null;
}
}
10. 总结
可以发现，在链表的问题中，通过两个的指针来提高效率是很值得考虑的一个解决方案，所以一定要记住这种解题思路。记住几种典型的链表问题解决方案，很多类似的题目都可以转换到熟悉的问题再解决。