透彻理解回文~单链表的逆序~

判断一个单链表是不是回文，主要有三种方法，不过如果要考虑空间复杂度的话，就只有常用的一种方法了。

这种方法很考验一个人的细心以及编程能力~

前两种方法比较简单我就不祥述了~

主要讲一下最后一种方法：直接上图了~

透彻理解回文~单链表的逆序~

下面附上code：

public static class Node {
public int value;
public Node next;

public Node(int data) {
this.value = data;
}
}

public static void main(String args[]) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(3);
head.next.next.next.next = new Node(2);
head.next.next.next.next.next = new Node(1);
printLinkedList(head);
isHuiWenList1(head);
isHuiWenList2(head);
isHuiWenList3(head);
}

/* 打印单链表 */
public static void printLinkedList(Node node) {
System.out.print("Linked List: ");
while (node != null) {
System.out.print(node.value + " ");
node = node.next;
}
System.out.println();
}

/*
* 需要额外空间复杂度O（n），这种方法在笔试中比较推荐。大概四路如下：新建一个堆栈，把list里面的元素一个一个 push进入堆栈中，全部都放进去以后，
* pop出来与单链表中的元素取出来进行比较，如果完全相等，则说明是回文，不然不是
*/
public static boolean isHuiWenList1(Node head) {
if (head == null || head.next == null) {
return true;
}
Stack<Node> st = new Stack<Node>();
Node cur = head;
/* 将元素压入堆栈 */
while (cur != null) {
st.push(cur);
cur = cur.next;
}
/* 判断单链表中的元素是否与堆栈pop出来的元素相等 */
while (head != null) {
if (head.value != st.pop().value) {
System.out.println("false");
return false;
} else {
head = head.next;
}
}
System.out.println("true");
return true;
}

/*
* 这种方法其实不怎么推荐，虽然它额外空间复杂度是O（n/2），但是编程相对来说有点难度，不过这里涉及到一种常用的思想：
* 定义一个指针，slow和fast，slow一次走一步，fast一次走两步，同时走，当fast走完全程的时候，slow刚好就在中点。
* 其他思想与方法一类似，也是定义一个堆栈，把单链表的元素放进去，再把它pop出来进行比较。
*/
public static boolean isHuiWenList2(Node head) {
Node fast = head;
Node slow = head;
if (head == null || head.next == null) {
return true;
}
/* 从这里开始走，一个走一步，一个走两步 */
if (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
/* 下面的slow此时是中点 */
Stack<Node> st = new Stack<Node>();
while (slow != null) {
st.push(slow);
slow = slow.next;
}
while (st.size() != 0) {
if (st.pop().value != head.value) {
System.out.println("false");
return false;
} else {
head = head.next;
}
}
System.out.println("true");
return true;
}

/*
* 下面这种方法空间复杂度为o（1），适合于在笔试中使用，很考验编程能力，主要是在逆序那里很容易出错，不过一旦理解了这种思想，逆序就不难理解了！
*/
public static boolean isHuiWenList3(Node head) {
if (head == null || head.next == null) {
System.out.println("true");
return true;
}

/* 找中点位置，也是通过两个指针来实现 */
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

/* 将中点右边的单链表进行逆序 */
Node n3 = null;
fast = slow.next;
slow.next = null;
while (fast != null) {
n3 = fast.next;
fast.next = slow;
slow = fast;
fast = n3;
}
/* 比较中点左边的元素和中点右边的元素是否相等，也即判断是否为回文 */
n3 = slow;
fast = head;
boolean res = true;
while (slow != null && fast != null) {
if (slow.value != fast.value) {
res = false;
break;
}
slow = slow.next;
fast = fast.next;
}
/* 将中点右边逆序的部分恢复过来，其实这里我也不太懂为什么要恢复过来，欢迎各位大神能来解答一下 */
slow = n3.next;
n3.next = null;
while (slow != null) {
fast = slow.next;
slow.next = n3;
n3 = slow;
slow = fast;
}
System.out.println(res);
return res;
}

透彻理解回文~单链表的逆序~

相关推荐