递归翻转链表

 //递归法翻转链表public ListNode reverse(ListNode node){if(node==null||node.next==null) return node;ListNode dummy = reverse(node.next);// 将 node.next.next 指针指向当前链表 nodenode.next.next = node;node.next = null;return dummy;//返回翻转后的链表}

非递归反转

public static void reversetList(HeroNode head) {
//如果当前链表为空，或者只有一个节点，无需反转，直接返回
if(head.next == null || head.next.next == null) {
return ;
}
//定义一个辅助的指针(变量)，帮助我们遍历原来的链表
HeroNode cur = head.next;
HeroNode next = null;// 指向当前节点[cur]的下一个节点
HeroNode reverseHead = new HeroNode(0, "", "");
//遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
//动脑筋
while(cur != null) {next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用cur.next = reverseHead.next;//将cur 的下一个节点指向新的链表的最前端
reverseHead.next = cur; //将cur 连接到新的链表上
cur = next;//让cur 后移
}
//将head.next 指向reverseHead.next , 实现单链表的反转
head.next = reverseHead.next;
}

头插法

   //为属性赋值newnode.data=temp;//判断当前链表是否第一次赋值if(header==null){header=newnode;}else{//将新节点连接到链表的头部newnode.next=header;//header永远存储第一个节点的地址header=newnode;}

尾插法

//添加节点到单向链表
//思路，当不考虑编号顺序时
//1. 找到当前链表的最后节点
//2. 将最后这个节点的next 指向新的节点
public void add(HeroNode heroNode) {
//因为head 节点不能动，因此我们需要一个辅助遍历temp
HeroNode temp = head;
//遍历链表，找到最后
while(true) {
//找到链表的最后
if(temp.next == null) {//break;
}
//如果没有找到最后, 将temp 后移
temp = temp.next;
}
//当退出while 循环时，temp 就指向了链表的最后
//将最后这个节点的next 指向新的节点
temp.next = heroNode;
}

删除特定元素的结点

//删除节点
//1. head 不能动，因此我们需要一个temp 辅助节点找到待删除节点的前一个节点
//2. 说明我们在比较时，是temp.next.no 和需要删除的节点的no 比较
public void del(int no) {
HeroNode temp = head;
boolean flag = false; // 标志是否找到待删除节点的
while(true) {
if(temp.next == null) { //已经到链表的最后
break;
}
if(temp.next.no == no) {
//找到的待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; //temp 后移，遍历
}
//判断flag
if(flag) { //找到//可以删除
temp.next = temp.next.next;
}else {
System.out.printf("要删除的%d 节点不存在\n", no);
}
}

链表选择排序

初始节点的值如果不正确会得到错误结果！！！

   public ListNode sortList(ListNode head) {
ListNode pre=  head;
ListNode tail = null;
ListNode curr = head;ListNode small = head;
ListNode smallpre = null;
if(head == null||head.next == null) return head;while (curr != null)
{
small = curr;smallpre = smallNodePre(curr);//small = smallNodePre(curr).next;if(smallpre != null){small = smallpre.next;smallpre.next = small.next;}curr = curr==small?curr.next:curr;if(tail == null)head = small;else tail.next = small;tail = small;
}
return head;}public ListNode smallNodePre(ListNode cur){ListNode pre = cur;//注意初始值ListNode small = cur;ListNode smallpre = null;ListNode current = cur.next;while (current != null){if(current.val<small.val){smallpre = pre;small = current;}pre = current;current = current.next;}return  smallpre;}

单链表归并排序

  public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head,ListNode tail){if(head == null) return head;if(head.next == tail){head.next = null;return head;}ListNode fast = head,slow = head;while (fast!=tail){fast = fast.next;slow=  slow.next;if(fast != tail)fast = fast.next;}ListNode mid = slow;ListNode li1= sortList(head,mid);ListNode li2= sortList(mid,tail);ListNode afterMerge = merge(li1,li2);return afterMerge;}public ListNode merge(ListNode head,ListNode tail){ListNode begin = new ListNode(0);ListNode temp = begin,temp1 = head,temp2 = tail;while (temp1 != null && temp2!=null){if(temp1.val<=temp2.val){temp.next =  temp1;temp1 = temp1.next;}else if(temp1.val> temp2.val){temp.next = temp2;temp2 = temp2.next;}temp = temp.next;}if(temp1!= null) temp.next =temp1;if(temp2!= null) temp.next = temp2;return begin.next;}

注意：如果把

if(temp1.val<=temp2.val)
{
temp.next = temp1;
temp1 = temp1.next;
}

改为小于号，等于的时候两者同时迁移，会筛选掉重复的元素（如1，2，2，3，得到的结果变成1，2，3），因此不能在两者相等时同时前移

不使用额外空间合并升序链表：迭代法

       public Node merge(Node head1, Node head2) {if (head1 == null || head2 == null) {return head1 != null ? head1 : head2;}Node head = head1.value < head2.value ? head1 : head2;Node cur1 = head == head1 ? head1 : head2;Node cur2 = head == head1 ? head2 : head1;Node pre = null;Node next = null;while (cur1 != null && cur2 != null) {if (cur1.value <= cur2.value) {pre = cur1;cur1 = cur1.next;} else {next = cur2.next;pre.next = cur2;cur2.next = cur1;pre = cur2;cur2 = next;}}pre.next = cur1 == null ? cur2 : cur1;}

不使用额外空间合并升序链表：递归法

递归法：

   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr)
return l2;
else if(l2 == nullptr)
return l1;
else if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;}
else 
{l2->next = mergeTwoLists(l1,l2->next);return l2;
}}