链表

链表是面试时被提及最频繁的数据结构。链表就是通过指针将一个个节点连接起来。链表是非连续的动态内存空间，链表的查找比数组慢，但是添加和删除比数组快。

链表声明

1 public class ListNode {2     int val;3     ListNode next;4     public ListNode(int val) {5         this.val = val;6         this.next = null;7     }8 }

链表的添加

1 public void insertList(ListNode head, int val) { 2     ListNode tempNode = new ListNode(val); 3     if (head == null) { 4         head = tempNode; 5     }else { 6         ListNode p = head; 7         while (p.next != null) { 8             p = p.next; 9         }10         p.next = tempNode;11     }12 }

链表的删除

1 public void deleteListNode(ListNode head, int val) { 2     if (head ==null) return;//为了鲁棒性 3     if (head.val == val) {
     //头节点为要删除节点 4         head = head.next; 5     } else { 6         ListNode p = head; 7         //删除节点需要知道前一个节点，所以判断p.next.val是不是和目标相等 8         while (p.next !=null && p.next.val != val) { 9             p = p.next;10         }11         if (p.next !=null) {12             p.next = p.next.next;//删除节点13         }14     }15 }

从尾到头打印链表

方法1：使用栈结构

1 public void printList1(ListNode head) { 2     if (head == null) return; 3     Stack
       
         stack = new Stack
        
         (); 4     ListNode p = head; 5     while (p != null) { 6         stack.push(p); 7         p = p.next; 8     } 9     while (!stack.isEmpty()) {10         p = stack.pop();11         System.out.print(p.val+" ");12     }13 }
        
       

 

方法2：递归

1 public void printList2 (ListNode head) {2     if (head != null) {3         if (head.next != null) {4             printList2(head.next);5         }6         System.out.print(head.val+" ");7     }8 }

注：递归的过程相当于栈。

反转单链表

1 public ListNode reverseList (ListNode head) { 2     ListNode pre = null; 3     ListNode next; 4     while (head != null) { 5         next = head.next; 6         head.next = pre; 7         pre = head; 8         head = next; 9     }10     return pre;11 }

反转双链表

1 public class DoubleNode { 2     public int val; 3     public DoubleNode pre; 4     public DoubleNode next; 5     public DoubleNode (int val){ 6         this.val=val; 7     } 8 } 9 public Node reverseList(Node head){10     DoubleNode pre=null;11     DoubleNode next=null;12     while(head!=null){13         //反转第一个节点14         next=head.next;//记录下一个节点15         head.next=pre;//反转当前节点:next指针指向上一个节点16         head.pre=next;//反转当前节点:pre指针指向下一个节点17         pre=head;//记录当前节点为下一个节点的pre18         head=next;//移动到下一个节点19     }20     return pre;//返回新头节点21 }

 

学习数据结构与算法的记录和整理，如有错误或意见请帮忙指出，以后会持续更新。。。。

参考书籍：

《程序员代码面试指南：IT名企算法与数据结构题目最优解》—左程云

《剑指Offer》 —何海涛