单链表翻转

leetcode206

递归

public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; ListNode rever = reverseList(head.next); //1->2->3->4,此时root=3，re=root.next=4,1->2->3,4->3 head.next.next = head; head.next = null; return rever; }

非递归

public static Node Traversing(Node root) { if(root ==null) return null; Node preNode = null; Node curNode = root; Node nextNode =null; while(curNode!=null) { nextNode = curNode.next; curNode.next =preNode; preNode =curNode; curNode = nextNode; } return preNode; }

两两交换链表中的节点

public ListNode swapPairs(ListNode head) { ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode q = dummyHead; while(q.next != null && q.next.next != null) { ListNode node1 = q.next; ListNode node2 = node1.next; ListNode nnext = node2.next; node2.next = node1; node1.next = nnext; q.next = node2; q = node1; } return dummyHead.next; }

K 个一组翻转链表

class Solution { public ListNode reverseKGroup(ListNode head, int k) { if(head == null) return null; ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode pre = dummyHead; ListNode end = dummyHead; while(end.next != null) { for(int i = 0; i < k && end != null; i++) { end = end.next; } if(end == null) break; //需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来 //初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾 //经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next //翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环 ListNode start = pre.next; ListNode pnext = end.next; end.next = null;//reverse:start~end,end后面断掉 pre.next = reverse(start);//pre：join第一部分前驱和翻转的链表 start.next = pnext;//end~start:join 已翻转和未翻转 pre = start; end = pre; } return dummyHead.next; } private ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null) { ListNode pnext = cur.next; cur.next = pre; pre = cur; cur = pnext; } return pre;//not return cur:cur =null this time. } }