写出正确链表代码的五个技巧

1.理解指针或引用的含义

2.警惕指针丢失和内存泄漏

3.利用哨兵简化实现难度

4.重点留意边界条件处理

5.举例画图,辅助思考

添加哨兵,即此链表是一个带头链表。哨兵是不存储数据的。因为哨兵一直存在,所有插入数据和删除数据相比不带头链表就没有二义性了。因此可以用一个统一的数据结构实现。

dummy 结点即哨兵:

ListNode dummy = new ListNode(0);
dummy.next = head;

运用技巧进行小练习:

反转单链表:

思路如图所示:

public ListNode Reverse(ListNode head){
	ListNode cur = head;
    ListNode pre = null;
    
    while(cur != null){
    	ListNode post = cur.next;
    	cur.next = pre;
    	pre = cur;
    	cur = post;       	
    }
    return pre;  
}

链表中环的检测:

思路如图所示:

  • 遍历链表中的数,将其放入到 set 中,如果 set 中重复出现这个数,那么说明这个链表有环。

    public boolean hasCycle(ListNode head){
    	Set<ListNode> set = new HashSet<>();
    	for(ListNode p = head; p != null; p=p.next){
            if(set.contains(p)){
                return true;
            }
            else{
                set.add(p);
            }
    	}
    	return false;
    }
    
  • 采用快慢指针,快指针每次走两步,慢指针每次走一步。如果有环的话,快指针一定会追上慢指针。

    public boolean hasCycle(ListNode head){
    	ListNode slow = head;
    	ListNode fast = head;
    	while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                return true;
            }
    	}
    	return false;
    }
    

两个有序链表合并:

思路如图所示:

为了使头部结点和其他结点处理起来是一致的,先给两个有序链表都安一个哨兵结点dummy,使其成为一个带头链表。

然后定义一个游标P,指向两个有序链表合并后的当前结点。

然后分别比较链表L1和链表L2的值,谁小P就指向谁,然后L1或L2向后移。不管L1,L2谁向后移了,P总归要向后移动。

最后当L1或L2移动到等于 null 时,直接拼接另一条仍不为 null 的链表。

public ListNode mergeTwoSortedLists(ListNode L1, ListNode L2){
	ListNode dummy = new ListNode(0);
	ListNode p = dummy;
	while(L1 != null && L2 != null){
        if(L1.val < L2.val){
            p.next = L1;
            L1 = L1.next;
        }
        else{
            p.next = L2;
            L2 = L2.next;
        }
        p = p.next;
	}
	if(L1 == null){
        p.next = L2;
	}
	else{
        p.next = L1;
	}
	retrun dummy.next;
}

移除单链表倒数第 n 个节点

思路如图所示:

安插哨兵dummy,设两个游标p,q;

q 先向后移动 n 步,然后只有 q.next 不为 null ,p 和 q 都向后移动一步;

当 q.next == null 时,停止移动,并且 p.next 指向 p.next.next;

public ListNode removeNthFromEnd(ListNode head,int n){
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode p = dummy;
	ListNode q = dummy;
	for(; n>0 && q.next != null; n--){
        q = q.next;
	}
	while(q.next != null){
        p = p.next;
        q = q.next;
	}
	p.next = p.next.next;
	return dummy.next;  
}

单链表中间节点:

思路如图所示:

  • 遍历两次链表,第一次计算出链表长度,第二次一个个遍历,在链表长度的二分之一处的结点即为单链表中间节点;

    public ListNode getMiddleNodeTwoPass(ListNode head){
    	ListNode p = head;
    	int len = 0;
    	for(; p!=null; p=p.next){
            len++;
    	}
    	p = head;
    	for(int i=0; i<=len/2; i++){
            p = p.next;
    	}
    	return p;
    }
    
  • 可以把这两次遍历合并起来,使用快慢指针,快指针一次走两步,慢指针一次走一步,当快指针的next为空时,快慢指针停止移动。

    public ListNode getMiddleNodeOnePass(ListNode head){
    	ListNode slow = head;
    	ListNode fast = head;
    	while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next;
    	}
    	return slow;
    }
    

tips:

结点 q 向后移动 n 步:

for(; n>0 && q.next != null; n--){
	q = q.next;
}