[LeetCode] 实现链表

坚持内卷，pua自己，不是你死，就是我活。

707. 设计链表

注意 在get 和add 和delete 写循环条件 是index 不是size
index就是要插入或删除的位置

class ListNode{    int  val;    ListNode next;    ListNode (){}    ListNode( int val){ this.val = val;    }}class MyLinkedList {    int  size;    ListNode head;    public MyLinkedList() { size = 0; head  = new ListNode(0);    } public int get(int index) { if(index <0 || index >=size)  return -1; ListNode cur = head; for( int i = 0; i<=index; i++){     cur  = cur.next; } return cur.val;    } public void addAtHead(int val) { addAtIndex(0,val);    } public void addAtTail(int val) { addAtIndex(size,val);    } public void addAtIndex(int index, int val) { if(index >size) return; if(index <0)  index = 0; ListNode cur = head; for( int i = 0; i <index; i++) cur = cur.next; ListNode t = new ListNode(val); t.next =  cur.next; cur.next = t; size++;    } public void deleteAtIndex(int index) { if(index >=size || index <0) return; ListNode cur = head; for( int i  = 0; i <index; i++) cur = cur.next; cur.next = cur.next.next; size--;    }}/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList obj = new MyLinkedList(); * int param_1 = obj.get(index); * obj.addAtHead(val); * obj.addAtTail(val); * obj.addAtIndex(index,val); * obj.deleteAtIndex(index); */

203. 移除链表元素

/** * 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 removeElements(ListNode head, int val) { ListNode i = new ListNode(-1,head); ListNode pre = i ; ListNode t = head; while(t !=null){     if(t.val == val){  pre.next = t.next;     }else{  pre = t;     }     t = t.next; } return i.next;    }}

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

法1：双指针法

/** * 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 reverseList(ListNode head) { ListNode  temp; ListNode   pre = null; ListNode    cur = head; while(cur != null){     temp  = cur.next;     cur.next  = pre;     pre = cur;     cur = temp; } return pre;    }}

法2：递归法

递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。

关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。

具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。

24. 两两交换链表中的节点

递归解法

其中我们应该关心的主要有三点：

1. 返回值

2. 调用单元做了什么

3. 终止条件

在本题中：

返回值：交换完成的子链表
调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换

/** * 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 ||head.next == null)    return head;ListNode next = head.next;head.next = swapPairs(next.next);//返回完成交换的子列表next.next = head;return next;    }}

非递归方法

/** * 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) { ListNode Ma  = new ListNode(0); Ma.next = head; ListNode pre = Ma; while(pre.next != null && pre.next.next  !=  null){//&&而不是||   ListNode  temp  = head.next.next;     pre.next = head.next;     head.next.next = head;     head.next = temp;     pre= head;//将pre指针前进一步     head= head.next;  } return Ma.next;    }}

19. 删除链表的倒数第 N 个结点

目的：得到要删除的的结点前一个结点

双指针做法 ， 让前后指针相隔n个结点，让两个指针循环下去，最后要删除的结点就是前一个结点，再得到删除结点的前一个结点，用temp.next = pre.next进行删除

class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) { ListNode  dummy  = new ListNode(-1); dummy.next = head; ListNode follow = dummy; ListNode pre =dummy;      for(int i = 0 ; i <n;i++){     follow = follow.next; } ListNode temp = null; while(follow != null){     temp  = pre;     follow = follow.next;     pre = pre.next; } temp.next= pre.next; return dummy.next;    }}