记录生活中的点点滴滴

0%

判断回文联表

接着链表,反转链表已经练得差不多了,这次来个比较难一点的,就是判断回文链表

首先,我们应该想一下回文链表的性质,也就是从最中间到两边,两条路的节点相等。

还有其实就是,这个链表和反转之后的新链表,两者是同样的。这也是它的性质。

所以,对应有两个方法:

①把原链表反转成一个新的链表,然后二者做比较。

②找到中间节点,反转之后的,和头结点开始比较

OK,先写第一个方法,反转成新的链表,但是要是新的链表,否则就冲突了。所以,第一种方法可以采取头插法,重新建立一个新链表,不能用迭代反转指针法去解决,因为反转指针是在原链表的基础上,改变了原链表,没有创建新的链表。

比较的话,就是迭代去比较每一个节点的值是否相等,不难。

综上所述,代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//头插法创建新链表,反转原来的链表
public ListNode reverse(ListNode head){
ListNode newHead = new ListNode();
while(head!=null){
ListNode temp = new ListNode(head.val);
temp.next = newHead.next;
newHead.next = temp;
head = head.next;
}
return newHead.next;
}
public boolean isPalindrome(ListNode head) {
ListNode newHead = reverse(head);
while(head!=null){
if(head.val!=newHead.val) return false;
head = head.next;
newHead = newHead.next;
}
return true;
}

接着看第二种方法,其实分三步:

  1. 先找中间节点
  2. 将中间节点之后的链表反转
  3. 比较两个链表是否想等

OK,先找中间节点,采用的是双指针法,一个步长为1,一个步长为2,迭代进行。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
//找中间节点
public ListNode findMid(ListNode head){
ListNode fast,slow;
fast = slow = head;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
//如果fast没有指向null,说明slow还需要前进一步
if(fast!=null) slow=slow.next;
return slow;
}

不过要注意循环退出的条件是 fast!=null && fast.next!=null 不然就会多走一步。

还有就是还得考虑链表长度是计数还是偶数的不同情况:

如果fast没有指向null,说明为奇数,此时slow在中间,还要往后移动一步。

然后反转以slow为头结点之后的链表,反转函数直接迭代改变指针法即可:

1
2
3
4
5
6
7
8
9
10
11
12
//反转链表
public ListNode reverse(ListNode head){
ListNode curr = head;
ListNode prev = null;
while(curr!=null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}

然后将原本的头结点和反转后的到的头结点传入比较函数,进行比较即可。

不过有一点需要注意,就是退出比较循环的条件中,是反转后的链表指针不等于空,而不是原本的链表指针。因为反转后的slow链表,它的长度是比较短的。

1
2
3
4
5
6
7
8
9
//比较两个链表是否想等,t2的长度要短一点
public boolean towList(ListNode t1,ListNode t2){
while(t2!=null){
if(t1.val!=t2.val) return false;
t1 = t1.next;
t2 = t2.next;
}
return true;
}