剑指offer第四天

25.复杂链表的复制

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

/*

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)

    {

        //一定注意考虑输入为空链表的情况

        if(pHead == null) return null;

        //第一步：克隆每个结点的值和next，并且将新节点放置在对应旧结点之后

        RandomListNode node = pHead;

        while(node != null){

            RandomListNode cloneNode = new RandomListNode(node.label);

            //cloneNode.label = node.label;

            cloneNode.next = node.next;

            node.next = cloneNode;

            node = cloneNode.next;

        }

        //第二步：克隆每个随机指针

        node = pHead;

        while(node != null){

            RandomListNode cloneNode = node.next;

            if(node.random != null)

            	cloneNode.random = node.random.next;

            node = cloneNode.next;

        }

        //第三步：拆分拼接的链表

        node = pHead;

        RandomListNode cloneHead = pHead.next;

        while(node != null){

            RandomListNode cloneNode = node.next;

            node.next = cloneNode.next;

            node = node.next;

            if(node != null)

            	cloneNode.next = node.next;

            else

                cloneNode.next = null;

        }

        return cloneHead;

    }

}

26.二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

/**

public class TreeNode {

    int val = 0;

    TreeNode left = null;

    TreeNode right = null;

    public TreeNode(int val) {

        this.val = val;

    }

}

*/

public class Solution {

    public TreeNode Convert(TreeNode pRootOfTree) {

        if(pRootOfTree == null) return null;

        if(pRootOfTree.left == null && pRootOfTree.right == null) return pRootOfTree;

        TreeNode left = Convert(pRootOfTree.left);

        TreeNode node = left;

        if(node == null)

            pRootOfTree.left = null;

        else{

            while(node.right != null)

            	node = node.right;

            pRootOfTree.left = node;

            node.right = pRootOfTree;

        }

        TreeNode right = Convert(pRootOfTree.right);

        pRootOfTree.right = right;

        if(right != null)

            right.left = pRootOfTree;

        return left != null ? left : pRootOfTree;

    }

}

27.字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Collections;

public class Solution {

    ArrayList<String> result = new ArrayList<String>();

    public ArrayList<String> Permutation(String str) {

        if(str == null) return null;

        char[] charArray = str.toCharArray();

        permutation(charArray,0);

        Collections.sort(result);

        return result;

    }

    public void permutation(char[] charArray,int beginIdx){

        if(beginIdx >= charArray.length) return;

        if(beginIdx == charArray.length-1){

            result.add(String.valueOf(charArray));

        }

        HashSet<Character> charSet = new HashSet<>();

        for(int i = beginIdx;i<charArray.length;i++){

            if(i == beginIdx){

                charSet.add(charArray[i]);

                permutation(charArray,beginIdx+1);

            }else if(i != beginIdx && !charSet.contains(charArray[i])){

                char temp = charArray[beginIdx];

                charArray[beginIdx] = charArray[i];

                charArray[i] = temp;

                permutation(charArray,beginIdx+1);

                temp = charArray[beginIdx];

                charArray[beginIdx] = charArray[i];

                charArray[i] = temp;

            }

        }

    }

}

巴特西

剑指offer第四天

25.复杂链表的复制

26.二叉搜索树与双向链表

27.字符串的排列

最新文章

热门文章