leetcode 94.二叉树的中序遍历
思路:我们可以定义三个指针进行操作。
首先分析一下为什么会用三个指针。我们知道,在链表中交换结点,我们需要更改结点的指针地址,在两个相邻结点的交换当中,我们需要知道这两个结点。举个例子:
比如1,2这两个相邻的结点,在自然数中,2的后面肯定是3,用链表形式表示,也就有了1->2->3
我们的目的是要交换1和2的位置,我们首先就需要知道2后面的指向3,这样我们才能把1的指针指向2后面的数,接着就需要用2指向1,这样就完成了一次交换。
但是,如果有多个数呢?比如1,2,3,4,5这个时候我们只对于两个结点的指针地址修改是不够的,当我们交换3,4这两个结点的时候,我们就必须要处理2这个数到底指向谁,所以,为了迭代一致,我们需要用3个指针进行操作。
回到第一个例子里,1->2->3,交换1,2,怎么用三个指针操作呢?很简单,我们只需要在1前面加上一个表头就行了,假设表头的元素值为-1,那么:-1->1->2->3,这样就解决了在头节点位置进行交换结点的问题了,之后汇总一下,就出来结果了。
注意:必须定义指向表头的指针,这样在交换节点之后,我们才能从表头再重新遍历这个链表,否则表头的指向发生了变化就不会指向链表的最前端了。
在代码中,为什么tmp只是向前移动了一次呢?而不是两次呢?因为我们的tmp在经过交换操作之后,已经移动了一次(tmp是两个结点的第一个结点,是前者;交换完之后变成了后者),所以我们只需要移动一次就够了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null)
return null;
ListNode dummy=new ListNode(-1);
dummy.next=head;
ListNode tmp=head;
ListNode tou=dummy;
while(tmp!=null&&tmp.next!=null){
ListNode p=tmp.next;
tou.next=p;
tmp.next=p.next;
p.next=tmp;
tmp=tmp.next;
tou=tou.next.next;
}
return dummy.next;
}
}