面试20分钟让写出来，请教大家！

Question

我去一家公司面试给20分钟时间，我没写出来。回来写了写还不是很完美，请大家指教（请给出代码）
1.有一个1->2->3->...->n->null的链表
public class Node｛
  String context；
  Node next；
｝
写一个方法public void replace（Node head）｛
 实现倒置这个链表 
｝
 
2.有两个未知的字符串A和B，写一个方法得出A和B的最大匹配子串。

Answer 1

1.
Node root = null;
if (head == null)
{
// empty linklist
// do nothing
}
else
{
Node currentNode = head;
Node nextNode = head.next;
currentNode.next = null;
while (nextNode != null)
{
    Node thirdNode = nextNode.next;
    nextNode.next = currentNode;
    currentNode = nextNode;
    nextNode = thirdNode;
}
root = currentNode;

Answer 2

2.
private void testSubstring(String strA, String strB)
{
int lengthA = strA.length();
int lengthB = strB.length();
String longStr = lengthA > lengthB ? strA : strB;
String shortStr = lengthA > lengthB ? strB : strA;
List maxSubstrList = new ArrayList();
for (int length = shortStr.length(); length > 0; length--)
{
for (int startIndex = 0; startIndex <= shortStr.length() - length; startIndex++)
{
String substr = shortStr.substring(startIndex, startIndex + length);
if (longStr.indexOf(substr) > -1)
{
maxSubstrList.add(substr);
}
}
if (maxSubstrList.size() > 0)
{
// 找到最大匹配子串
break;
}
}
System.out.println(maxSubstrList);
}

Answer 3

public class LinkedList {
private Node header;

/**
 * @return the header
 */
public Node getHeader() {
return header;
} /**
 * @param header the header to set
 */
public void setHeader(Node header) {
this.header = header;
}

public void printListContext(){
if (this.header == null){
System.out.println("Null");
return;
}
Node temp = this.header;
while(temp != null){
System.out.print(temp.getContext() + "-->");
temp = temp.getNext();
}
System.out.print("null");
System.out.println();
}

public void resverce(){
if (this.header == null || this.header.getNext() == null){
return;
}

Node current = this.header,tempNext = this.header.getNext();
int cnt = 0;
while(tempNext != null){
cnt ++;
Node temp = current;
current = tempNext;
tempNext = tempNext.getNext();
if (cnt == 1){
temp.setNext(null);
}
current.setNext(temp);
}
this.header = current;
}

public void buildLinkedList(){
Node n4 = new Node("4",null);
Node n3 = new Node("3",n4);
Node n2 = new Node("2",n3);
Node n1 = new Node("1",n2);
Node n0 = new Node("0",n1);

this.header = n0;
} /**
 * @param args
 */
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.buildLinkedList();

ll.printListContext();
ll.resverce();
ll.printListContext();

}

class Node {
private String context;
private Node   next;
public Node(String context,Node n){
this.context = context;
this.next = n;
}
/**
 * @return the context
 */
public String getContext() {
return context;
}
/**
 * @return the next
 */
public Node getNext() {
return next;
}
/**
 * @param next the next to set
 */
public void setNext(Node next) {
this.next = next;
}
}
}

Answer 4

Node current = this.header,tempNext = this.header.getNext();
int cnt = 0;
while(tempNext != null){
  cnt ++;
  Node temp = current;
  current = tempNext;
  tempNext = tempNext.getNext();
  if (cnt == 1){
    temp.setNext(null);
  }
  current.setNext(temp);
}
this.header = current;这是反转的算法

Answer 5

非常感谢vdragon(紫龙) 和daniel_kaka() 两位朋友！谢谢

Answer 6

public static void getMaxPattern(String strA, String strB) {
  //只要有一个null，就返回null
  if (strA == null||strB == null||strA.trim().equals("") ||strB.trim().equals("")){
    System.out.println("");
    return;
  }
  int lengthA = strA.length();
  int lengthB = strB.length();
  String longStr = lengthA > lengthB ? strA : strB;
  String shortStr = lengthA > lengthB ? strB : strA;
  Map<Integer,List<String>> maxSubstrList = new HashMap<Integer,List<String>>();
  for (int length = shortStr.length(); length > 0; length--) {
    for (int startIndex = 0; startIndex<=shortStr.length() - length; startIndex++) {
      String substr = shortStr.substring(startIndex, startIndex + length);
      if (longStr.indexOf(substr) > -1) {
        int len = substr.length();
        List<String> list;
        if (maxSubstrList.containsKey(len)){
        list = (List<String>)maxSubstrList.get(len);
      }else{
        list = new ArrayList<String>();
      }
      list.add(substr);
      maxSubstrList.put(len, list);
    }
   }
  }
  // 找到最大匹配子串
  int maxLen = 0;
  for(int nKey:maxSubstrList.keySet()){
    maxLen = maxLen>nKey?maxLen:nKey;
  }
  List<String> maxList = maxSubstrList.get(maxLen);
  for(String str:maxList){
    System.out.println(str);
  }
}

Answer 7

我的最简单
    public static String matcher(String s1, String s2) {       // the mini length String       String shortString = (s1.length() < s2.length()) ? s1 : s2;       // the max length String       String longString = (s1.length() < s2.length()) ? s2 : s1;        for (int i = shortString.length(); i > 0; i--) {           for (int j = 0; j <= shortString.length() - i; j++) {              String subs = shortString.substring(j, j + i);              if (longString.indexOf(subs) > -1) {                  return subs;              }           }       }        return "";     }

Answer 8

用递归不知道可不可以
public void replace(Node head){
while(head.context!=null){
if(head.context==null){
return;
}

Sting str=head.context;
head.context=head.next.context;
head.next.context=str;

replace(head.next);
}
}

Answer 9

二十分钟内谁能用KMP算法做出第二题吗.
不要查书.

Answer 10

Node x = null;
Node y = head.next;while (y != null) {
    head.next = x;
    x = head;
    head = y;
    y = y.next;
}head.next = x;

Answer 11

    public static String g(String a, String b) {
        String str = "";        int x = a.length();
        int y = b.length();
        String t = "";        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                for (int k = j + 1; k < x; k++) {
                    t = a.substring(j, k);
                    if (t.equals(b.substring(i, i + k - j))) {
                        str = str.length() < k - j ? t : str;
                    } else {
                        break;
                    }
                }
            }
        }        return str;
    }

Answer 12

有点小毛病
if ((i + k - j) <= y && t.equals(b.substring(i, i + k - j))) {
    str = str.length() < k - j ? t : str;
} else {
    break;
}