当前位置:   article > 正文

单链表面试题---移除链表元素和翻转链表

单链表面试题---移除链表元素和翻转链表

1.移除链表元素

题目链接:203. 移除链表元素 - 力扣(LeetCode)

解法一:定义两个指针

分别定义两个指针,分别为cur和prev,让cur=head.next,让prev=head。

如下图

cur指针是用来确定该节点的数据是否为要删除的数据,如果cur指向的节点的数据为要删除的数据,则我们让prev.next=cur.next,然后再让cur=cur.next。如果cur指向的节点中的数据不是要删除的,则让prev=cur,cur=cur.next。

过程图

假设11是我们要删除的数据,则观察图,看到cur指向的数据为11,则执行prev.next=cur.next,cur=cur.next

然后发现cur指向的节点中的数据不是要删除的数据,我们同时让prev=cur,cur=cur.next。

持续上面的步骤,一直到cur指向空。

但是以上这种写法,没有解决要删除的节点在头节点的问题,所以我们要将这一情况单独拿出来解决。

  1. public ListNode removeElements(ListNode head, int val) {
  2. if(head==null){
  3. return head;
  4. }
  5. ListNode cur=head.next;
  6. ListNode prev=head;
  7. while(cur!=null){
  8. if(cur.val==val){
  9. prev.next=cur.next;
  10. cur=cur.next;
  11. }else{
  12. prev=cur;
  13. cur=cur.next;
  14. }
  15. }
  16. //解决头节点为删除节点的情况
  17. if(head.val==val){
  18. head=head.next;
  19. }
  20. return head;
  21. }

解法二:定义一个新链表

我们可以定义一个新链表,然后将不是要删除的节点放到新节点,最后放回newHead.next。 

 

代码实现

  1. public ListNode removeElements(ListNode head, int val) {
  2. if(head==null){
  3. return null;
  4. }
  5. ListNode newHead=new ListNode();
  6. ListNode cur=head;
  7. ListNode cur2=newHead;
  8. while(cur!=null){
  9. if(cur.val!=val){
  10. cur2.next=cur;
  11. //注意让cur2=cur
  12. cur2=cur;
  13. }
  14. cur=cur.next;
  15. }
  16. cur2.next=null;
  17. return newHead.next;
  18. }

2. 翻转链表

翻转一个链表,我们可以定义一个cur=head.next,接着让cur指向的节点进行头插。

 代码实现

  1. public ListNode reverseList(ListNode head) {
  2. if(head==null){
  3. return null;
  4. }
  5. ListNode cur=head.next;
  6. //要先将head.next变为空,因为后面head会变
  7. head.next=null;
  8. while(cur!=null){
  9. //记录cur的下一个节点,因为cur.next后面会变
  10. ListNode curN=cur.next;
  11. cur.next=head;
  12. head=cur;
  13. cur=curN;
  14. }
  15. return head;
  16. }

 

 

 

 

 

 

 

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/909594
推荐阅读
相关标签
  

闽ICP备14008679号