Jinzhe Shan

剑指offer|解题代码-1-LinkedList

目录：

LinkedList

​ 003-从尾到头打印链表 √

​ 014-链表中倒数第k个结点 √

​ 015-反转链表 √

​ 016-合并两个或k个有序链表 √

​ 025-复杂链表的复制

​ 036-两个链表的第一个公共结点 √

​ 055-链表中环的入口结点 √

​ 056-删除链表中重复的结点 √

LinkedList

003-从尾到头打印链表 √

题目描述: 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路：所以逆序的操作都应该想到 stack 这个先进后出的数据结构

  1. 建立一个辅助栈 stack 和一个存储结构 ArrayList
  2. 将 原来链表中的值 一个个 push到 stack中
  3. 将 stack中存储的值 一个个 pop 到 ArrayList

解题代码：（Java）

/**
*    Q: 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // 0. special case []
        if(listNode == null){
            ArrayList list = new ArrayList();
            return list;
        }
        // 1. Create assistant Stack and new ListNode for store data
        Stack<Integer> temp = new Stack<>();
        ArrayList<Integer> newList = new ArrayList<>();
        ListNode t = listNode;
        // 2. push to Stack in order
        while(t != null){
            temp.push(t.val);
            t = t.next;
        }
        // 3. pop to new list in order which reversed order
        while(!temp.isEmpty()){ // check whether stack is empty? ---> .isEmpty() 
            newList.add(temp.pop());
        }
        return newList;
    }
}

014-链表中倒数第k个结点 √

题目描述: 输入一个链表，输出该链表中倒数第k个结点。

思路： 快慢指针 1. 定义两个指针 P1 P2 2. P1 先向后寻址 k-1 次 3. P1 P2同时向后寻址，当P1 == NULL 时，P2所指向的恰好为倒数第k个结点

解题代码：（Java）

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*
思路：
定义两个指针 P1 P2
P1 先向后寻址 k-1 次
然后P1 P2同时向后寻址，当P1 == NULL 时，P2所指向的恰好为倒数第k个结点
*/ 
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null||k<=0)
        return null;
    ListNode P1 = head;
    ListNode P2 = head;
    for(int i = 0; i < k-1;i++){
        if(P1.next!=null)
            P1 = P1.next;
        else 
            return null;
    }
    while(P1.next!=null){
        P1 = P1.next;
        P2 = P2.next;
    }
    return P2;
    }
}

015-反转链表 √

Q：输入一个链表，反转链表后，输出新链表的表头。

思路： 1. 找到反转后链表的 headNode 当cur.next == null 时， headNode = cur 2. 保证反转链表不出现断裂， 保存好 cur.next 结点

解题代码：（Java）

*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
    ListNode pReversedHead = null;
    ListNode pCur  = head;
    ListNode pPrev = null;

    while(pCur !=null){
        ListNode pNext = pCur.next;
        if(pNext == null) pReversedHead = pCur;
        pCur.next = pPrev; // 反向链表 的 Next 是之前的上一个结点 prev
        pPrev = pCur;// 反向链表现在的节点 是之后的 prev节点
        pCur = pNext;
    }
    return pReversedHead;
    }
}

016-合并两个或k个有序链表 √

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

思路：

解题代码：（Java）

递归版本

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    // 递归版本
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val <= list2.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}

非递归版本

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    // 非递归版本
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode list3 = new ListNode(-1);
        ListNode head3 = list3;
        while(list1!=null&&list2!=null){
            if(list1.val <= list2.val){
                list3.val = list1.val;
                list1 = list1.next;
            }else {
                list3.val = list2.val;
                list2 = list2.next;
            }
            list3 = list3.next;
        }
        while(list1 != null){
            list3.val = list1.val;
            list1 = list1.next;
            list3 = list3.next;
        }
        while(list2 != null){
            list3.val = list2.val;
            list2 = list2.next;
            list3 = list3.next;
        }
        return head3;
        // 报错  java.lang.NullPointerException
    }
}

025-复杂链表的复制

题目描述: 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路： 时间和空间效率最高的解法是复制+拆分 1. 复制原节点A后的A'放在A节点后 2. 遍历原节点A的random节点B，并将复制节点A'的random节点连接节点B' 3. 将链表拆分成 A->B>C 与 A'->B'->C'

解题代码：（Java）

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
/*

public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        // 0. 空链表情况
        if (pHead == null){
            return null;
        }
        // 1. 复制原节点A后的A'放在A节点后
        RandomListNode cur = pHead;
        while(cur !=null){
            RandomListNode repeat = new RandomListNode(cur.label);
            repeat.next = cur.next;
            cur.next = repeat;
            cur = cur.next;
        }

        //2. 遍历原节点A的random节点B，并将复制节点A'的random节点连接节点B'
        cur = pHead;
        while(cur != null){
            cur.next.random = cur.random.next; // 自己画个图比较好理解
            cur = cur.next.next;
        }

        // 3. 将链表拆分成 A->B>C 与 A'->B'->C'
        cur = pHead; // A
        RandomListNode newHead = pHead.next; // A'
        //RandomListNode newCur = newHead;//A'
        while(cur !=null){
            RandomListNode cloneNode = cur.next;//A'
            cur.next = cur.next.next; // A -> B
            cloneNode.next = cloneNode.next.next;// A'->B'
            cur = cur.next;// A ---> B
        }
        return newHead;
    }
}

036-两个链表的第一个公共结点 √

题目描述: 输入两个链表，找出它们的第一个公共结点。

Date: 20190918

思路：

首先，存在公共结点的两个链表是Y字形的，而不可能出现X形的，意味着从第一个公共结点开始，它们的后续结点都相同。 1. 计算两个List的长度，得到长度查Dif 2. 长的List 先遍历 Dif次后，与短的List依次比较结点 3. 当结点相同，则为第一个公共结点

解题代码：（Java）

/*
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;
        }
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        int pHead1Length = 0;
        int pHead2Length = 0;
        while(cur1!=null){
            pHead1Length ++;
            cur1 = cur1.next;
        }
        while(cur2!=null){
            pHead2Length ++;
            cur2 = cur2.next;
        }
        cur1 = pHead1;
        cur2 = pHead2;
        if (pHead1Length >= pHead2Length){
            int lengthDif = pHead1Length - pHead2Length;
            while(lengthDif>0){
                cur1 = cur1.next;
                lengthDif --;
            }
        }
        else{
            int lengthDif = pHead2Length - pHead1Length;
            while(lengthDif>0){
                cur2 = cur2.next;
                lengthDif --;
            }
        }
        while(cur1!=null && cur2 !=null && cur1 != cur2){
            cur1  = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

055-链表中环的入口结点 √

题目描述: 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路： 1. 快慢指针，直到相遇 2. 慢指针回到head，快指针速度降为一次一步，再次相遇则为环入口 3. 需要注意快指针的边界和测试用例的情况

解题代码：（java）

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
/*
思路：
1. 快慢指针，直到相遇
2. 慢指针回到head，快指针速度降为一次一步，再次相遇则为环入口
3. 需要注意快指针的边界和测试用例的情况
*/

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead == null || pHead.next == null)
            return null;

        ListNode pFast = pHead;
        ListNode pSlow = pHead;

        while(pFast != null && pFast.next !=null){
            pFast = pFast.next.next;
            pSlow = pSlow.next;
            if(pFast == pSlow){
                pSlow = pHead;
                while(pFast != pSlow){
                    pFast = pFast.next;
                    pSlow = pSlow.next;
                }
                if(pFast == pSlow)
                    return pFast;
            }
        }
        return pSlow;
    }
}

056-删除链表中重复的结点 √

题目描述 : 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路: 1. 创建头结点，解决 1-1-2-2-3-3 这种一开始就遇到一样的问题 2. 创建preNode 确定前一个不重复的结点 3. 创建curNode 一直遍历，遇到重复的结点（值相同）就继续往后， 若值不相同，令preNode.next 指向 curNode.next curNode = curNode.next

解题代码：（Java）

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
/*
思路:
1. 创建头结点，解决 1-1-2-2-3-3 这种一开始就遇到一样的问题
2. 创建preNode 确定前一个不重复的结点
3. 创建curNode 一直遍历，遇到重复的结点（值相同）就继续往后，
   若值不相同，令preNode.next 指向 curNode.next
   curNode = curNode.next
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode headNode = new ListNode(0);
        headNode.next = pHead;
        ListNode preNode = headNode;
        ListNode curNode = pHead;

        while(curNode != null){
            // move and delete
            if(curNode.next != null && curNode.val == curNode.next.val){
                while(curNode.next != null && curNode.val == curNode.next.val){
                curNode = curNode.next;
                }
                preNode.next = curNode.next;
                curNode = curNode.next;
            }
            // move
            else{
                preNode = curNode;
                curNode = curNode.next;
            }
        }
        return headNode.next;
    }
}

Published

Category

interview

Tags

Contact