链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
反转链表
1、问题
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1，长度为n，反转该链表后，返回新链表的表头。
数据范围：0≤n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n) 。
2代码实现
public ListNode ReverseList(ListNode head) { //递归终止条件 if (head==null||head.next == null) { return head; } //反转下一个 ListNode newHead=ReverseList(head.next); //逆转本级节点 head.next.next=head; //尾部设置空节点 head.next=null; return newHead; }
合并两个排序的链表
1、问题
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：0≤n≤1000，-1000 ≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
2、代码实现
public ListNode Merge(ListNode list1, ListNode list2) { ListNode head = new ListNode(-1); ListNode newhead=head; while (list1 != null || list2 != null) { if (list1 == null) { head.next = list2; head=head.next; list2 = list2.next; } else if (list2 == null) { head.next = list1; head=head.next; list1 = list1.next; } else if (list1.val <= list2.val) { head.next = list1; head=head.next; list1 = list1.next; } else { head.next = list2; head=head.next; list2 = list2.next; } } return newhead.next; }
删除链表的节点
1、问题
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
1.此题对比原题有改动
2.题目保证链表中节点的值互不相同
3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
数据范围:
0<=链表节点值<=10000
0<=链表长度<=10000
2、代码实现
public ListNode deleteNode (ListNode head, int val) { //创建一个结点 ListNode newhead=new ListNode(-1); //将上一个节点作为链表的头结点 newhead.next=head; //将新的链表赋值个head head=newhead; //判断循环 while (newhead.next != null) { //如果下一个节点的值和要求的值相等 if(newhead.next.val==val){ //将新链表的节点的下一个节点设置为链表的下一个节点的下一个节点 newhead.next=newhead.next.next; }else{ //不相等的话就遍历下一个节点 newhead=newhead.next; } } //返回head链表的下一个节点 return head.next; }
总结
链表中如果将x节点赋值给y节点，那么对y节点的操作同样会影响到x节点的值，这是因为y节点和x节点的地址是一样的，也就是说是同一个节点，所以说赋值操作不会获取新的地址，只是这个地址多了一个映射而已。除非你是进行new的操作，这样就会有新的地址，就是不同的节点喽 递归进行操作的时候，重复引用的方法上面的语句是会提前运行，后面的语句得等递归完了再运行哦。
