反转链表

https://leetcode-cn.com/problems/reverse-linked-list/submissions/

1.想法:

  1. 当链表的长度为0,或1时候我们不用操作已经完成反转
  2. 当链表长度大于1,那么我们需要记录的是前一个链表节点,和现在需要反转的链表节点和该链表的下一节点


    image.png

当我们原来的next为null的时候说明我们的链表反转完成了,此时我们只需要将将来的next赋值给要反转的链表就可以完成反转,否则,我们需要做3件事1.将将来的next节点1,赋值给节点2的next,然后将3现在要反转的节点变成3,将来的next变成1

就是1.now.next =last; 2. next.next =now ; 3.now = last;

2.代码:

迭代写法:

public ListNode reverseList(ListNode head) {
       if(head == null||head.next == null)return head;
       else{
           ListNode last = null;
           while(head!= null){
               if(head.next != null){
                   ListNode next = head.next;
                   head.next = last;
                   last = head;
                   head = next;
               }else{
                   head.next = last;
                   head = null;
               }
           }
           return head;
       }
    }

递归写法:

 public ListNode reverseList(ListNode head) {
       if(head == null){
           return null;
       }else{
           return getReverseList(null,head);
       }
    }

    private ListNode getReverseList(ListNode head, ListNode next) {
        if(next == null){
            return head;
        }else{
            ListNode newNext = next.next;
            next.next = head;
            return getReverseList(next,newNext);
        }
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容